eolymp
bolt
Try our new interface for solving problems
Problems

Разбиение числа

Разбиение числа

Time limit 1 second
Memory limit 64 MiB

Для заданного положительного 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
Author Темури Заркуа
Source Ужгород. Международная летняя школа для участников ACM ICPC. Вторая лига. День Темури Заркуа,18 августа 2017 года