ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1763. Блоха-знаток

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Блоха запрыгнула на круглый стол для игры в «Что? Где? Когда?» незадолго до начала очередной игры. На секторах стола уже были разложены конверты с вопросами. Блоха решила заранее прочитать все вопросы, чтобы у неё было больше времени подумать над ответами.
Problem illustration
Круглый игровой стол поделён на n секторов, занумерованных по часовой стрелке числами от 1 до n. Блоха запрыгнула на первый сектор. С него она может либо перебежать на соседний, либо перепрыгнуть через два сектора (например, если стол делится на 12 секторов, то с сектора номер 1 блоха может за одно действие попасть на сектора с номерами 2, 4, 10 и 12). Блоха хочет побывать на каждом секторе ровно один раз и вернуться обратно на первый сектор, откуда она спрыгнет и убежит думать над вопросами. Определите, сколькими способами она сможет совершить своё путешествие.

Исходные данные

В единственной строке записано целое число n (6 ≤ n ≤ 109) — количество секторов на игровом столе.

Результат

Выведите количество способов побывать на всех секторах ровно один раз и вернуться на первый сектор по модулю 109 + 9.

Пример

исходные данныерезультат
6
12
Автор задачи: Игорь Чевдарь
Источник задачи: XIV чемпионат Урала по спортивному программированию, 10 апреля 2010 г.