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

Как рассадить?

Как рассадить?

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

Некая организация устроила мероприятие для N пар близняжек, каждая из которых состоит из брата и сестры. На банкете решили усадить их всех за круглым столом. Сколькими различными способами это можно сделать, если парни и девушки хотят чередоваться и для разнообразия никакую пару близнецов не хотят посадить рядышком.

Две рассадки будут считаться различными, если не существует ни одного перемещения по кругу сидящих за столом в одной из этих рассадок, которая даст полное совпадение со второй рассадкой.

Вхідні дані

В единственной строке входного файла целое число N (0N500).

Вихідні дані

В единственной строке – ответ задачи.Ответ выдать по модулю 1000000009 (10^9+9).

Приклад

Вхідні дані #1
1

Вихідні дані #1
0