Блоха запрыгнула на круглый стол для игры в «Что? Где? Когда?» незадолго до начала очередной игры. На секторах стола уже были разложены конверты с вопросами. Блоха решила заранее прочитать все вопросы, чтобы у неё было больше времени подумать над ответами.

Круглый игровой стол поделён на n секторов, занумерованных по часовой стрелке числами от 1 до n. Блоха запрыгнула на первый сектор. С него она может либо перебежать на соседний, либо перепрыгнуть через два сектора (например, если стол делится на 12 секторов, то с сектора номер 1 блоха может за одно действие попасть на сектора с номерами 2, 4, 10 и 12). Блоха хочет побывать на каждом секторе ровно один раз и вернуться обратно на первый сектор, откуда она спрыгнет и убежит думать над вопросами. Определите, сколькими способами она сможет совершить своё путешествие.

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

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