Competitions
ISSPS`13 Wave 2 Day 5
Как рассадить?
Некая организация устроила мероприятие для N пар близняжек, каждая из которых состоит из брата и сестры. На банкете решили усадить их всех за круглым столом. Сколькими различными способами это можно сделать, если парни и девушки хотят чередоваться и для разнообразия никакую пару близнецов не хотят посадить рядышком.
Две рассадки будут считаться различными, если не существует ни одного перемещения по кругу сидящих за столом в одной из этих рассадок, которая даст полное совпадение со второй рассадкой.
Input data
В единственной строке входного файла целое число N (0 ≤ N ≤ 500).
Output data
В единственной строке – ответ задачи.Ответ выдать по модулю 1000000009 (109+9).
Examples
Input example #1
1
Output example #1
0