Скільки збалансованих троїчних

Троїчний запис вважається збалансованим, якщо в ньому міститься однакова кількість парних і непарних цифр (де 0 вважається парною цифрою), і при цьому в жодному префіксі (початковій частині) кількість парних цифр не перевищує кількість непарних цифр.

Для заданого числа $N$ (0 < N \le 10^6) потрібно визначити загальну кількість збалансованих троїчних записів довжини $N$. Результат слід подати за модулем 1000000009 (10^9+9).