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

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

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

Обмеження:

0 < N ≤ 10^6.

Вхідні дані

У першому рядку вхідного файлу знаходиться число N.

Вихідні дані

В єдиному рядку виведіть відповідь на задачу.

Приклади