eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сколько сбалансированных троичных

Сколько сбалансированных троичных

Троичную запись назовем сбалансированной, если в ней одинаковое количество чётных и нечётных цифр (0 — чётная цифра) и при этом ни в одном префиксе (начале) количество чётных цифр не превосходит количество нечётных цифр.

Для заданного числа N определить общее количество сбалансированных троичных записей длины N. Результат выдать по модулю 1000000009 (109+9).

Ограничения.

0 < N ≤ 106.

Входные данные:

В первой строке входного файла — число N.

Выходные данные:

В единственной строке – ответ задачи.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
2
Вихідні дані #1
2