Шляхи кораблів#3249
Румунський турист вирушив у подорож Середземним морем. Він прибув до одного з міст на трьох островах, які він планує відвідати. На кожному острові розташовано рівно міст, у кожному з яких є порт. Турист планує розпочати свою подорож з міста, у якому він зараз перебуває, потім відвідати інші 3N - 1 міст (кожне рівно один раз) і повернутися до міста, з якого стартував, щоб після цього повернутися додому.
На жаль, на всіх дорогах трьох островів знаходяться канібали. Саме тому подорож дорогою між двома містами одного острова дуже небезпечна і, відповідно, заборонена. На щастя, завжди існують морські маршрути. Кожна пара міст, які розташовані на різних островах, з'єднана морським маршрутом. Між містами одного острова маршрути відсутні.
Турист хоче дізнатися, скільки існує способів спланувати свою подорож трьома островами.
Вхідні дані містять одне число (1 \leq N \leq 30) — кількість міст на кожному з островів.
Виведіть одне число — кількість способів, якими турист зможе спланувати подорож. Дві подорожі вважаються однаковими, якщо послідовності міст однакові, або якщо послідовність міст першої подорожі збігається з послідовністю міст другої подорожі, прочитаної у зворотному порядку (наприклад, якщо на кожному острові є одне місто, номер якого збігається з номером острова, то подорожі 1-2-3-1 та 1-3-2-1 вважаються однаковими).
Приклад 1