Problems
Разбиение числа
Разбиение числа
Для заданного положительного N определить количество таких разбиений этого числа на положительные слагаемые, когда суммы слагаемых на четных и нечетных местах равны и при этом ни в одном начале выражения сумма слагаемых на четных местах не превосходит сумму слагаемых на нечетных местах (нумерация слагаемых с 1).Например, для N=6, таких разбиений всего 5:
3+3, 2+2+1+1, 2+1+1+2, 1+1+2+2, 1+1+1+1+1+1.
Результат выдать по модулю 1000000009 (10^9
+9).
####Ограничения0 < N ≤ 10^6
.
####Входные данныеВ единственной строке входного файла – число N.
####Выходные данныеВ единственной строке – ответ задачи.
Examples
Input example #1
6
Output example #1
5
Input example #2
7
Output example #2
0