eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Шляхи кораблів

Шляхи кораблів

Ліміт часу 1 секунда
Ліміт використання пам'яті 16 MiB

Румунський турист відправився у подорож по Середземному морю. Він прибув у одне з міст на трьох островах, які він збирався відвідати. На кожному острові розміщено у точності N міст, у кожному з яких є порт. Турист планує розпочати свою подорож з міста, у якому він зараз знаходиться, потім відвідати інші 3*N-1 міст (кожне у точності один раз) і повернутись у місто, з якого він стартував, щоб легко було дістатись після подорожі додому.

На жаль, на усіх дорогах трьох островів знаходяться каннібали. Ось чому подорож по дорозі між двома містами одного острова дуже небезпечна і відповідно, заборонена. На щастя, завжди існують корабельні маршрути. Кожна пара міст, які не знаходяться на одному острові, з'єднана корабельним маршрутом. Між містами одного острова маршрути відсутні.

Турист хоче взнати, скількома способами він зможе зпланувати свою подорож по трьом островам.

Вхідні дані

Вхідні дані містять одне число N (1N30) - кількість міст на кожному з 3-х островів.

Вихідні дані

Вивести одне число - кількість способів, якими турист зможе зпланувати подорож. Дві подорожі вважаються однаковими, якщо послідовності 3*N міст однакові, або якщо послідовність 3*N міст першої подорожі співпадає з послідовністю 3*N міст другої подорожі, взятої у протилежному порядку (наприклад, якщо на кожному острові є одне місто, номер якого співпадає з номером острова, то подорожі 1-2-3-1 та 1-3-2-1 вважаються однаковими).

Приклад

Вхідні дані #1
2
Вихідні дані #1
16
Автор Mugurel Ionut Andreica
Джерело Romanian Open Contest, December 2001