Задачи
Сколько сбалансированных троичных
Сколько сбалансированных троичных
Троичную запись назовем сбалансированной, если в ней одинаковое количество чётных и нечётных цифр (0 — чётная цифра) и при этом ни в одном префиксе (начале) количество чётных цифр не превосходит количество нечётных цифр.
Для заданного числа N определить общее количество сбалансированных троичных записей длины N. Результат выдать по модулю 1000000009 (109
+9).
Ограничения.
0 < N ≤ 106
.
Входные данные:
В первой строке входного файла — число N.
Выходные данные:
В единственной строке – ответ задачи.
Входные данные #1
2
Выходные данные #1
2