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