Розбиття числа

Для заданого додатного числа $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 \le 10^6.