Блоха запрыгнула на круглый стол для игры в «Что? Где? Когда?» незадолго до
начала очередной игры. На секторах стола уже были разложены конверты с вопросами.
Блоха решила заранее прочитать все вопросы, чтобы у неё было больше времени подумать
над ответами.
Круглый игровой стол поделён на n секторов, занумерованных по часовой стрелке числами от 1 до n. Блоха запрыгнула на первый сектор. С него она может либо перебежать на соседний, либо перепрыгнуть через два сектора (например, если стол делится на 12 секторов, то с сектора номер 1 блоха может за одно действие попасть на сектора с номерами 2, 4, 10 и 12). Блоха хочет побывать на каждом секторе ровно один раз и вернуться обратно на первый сектор, откуда она спрыгнет и убежит думать над вопросами. Определите, сколькими способами она сможет совершить своё путешествие.
Исходные данные
В единственной строке записано целое число n (6 ≤ n ≤ 109) — количество секторов на игровом столе.
Результат
Выведите количество способов побывать на всех секторах ровно один раз и вернуться на первый сектор по модулю 109 + 9.
Пример
исходные данные | результат |
---|
6 | 12 |
Автор задачи: Игорь Чевдарь
Источник задачи: XIV чемпионат Урала по спортивному программированию, 10 апреля 2010 г.