Як розсадити?#5980
Деяка організація влаштувала захід для пар близнюків, кожна з яких складається з брата і сестри. На банкеті вирішили посадити їх усіх за круглим столом. Скількома різними способами це можна зробити, якщо хлопці та дівчата хочуть чергуватися, і для різноманітності жодну пару близнюків не хочуть посадити поряд.
Дві розсадки вважаються різними, якщо не існує жодного переміщення по колу тих, хто сидить за столом в одній з цих розсадок, яке дасть повне співпадіння з другою розсадкою.
В єдиному рядку вхідного файлу задано ціле число (0 \leq N \leq 500).
В єдиному рядку виведіть відповідь на задачу. Відповідь подайте за модулем (10^9+9).
Приклад 1