Скільки шаблонів?

Арифметичні вирази можна записувати у бездужковій формі. Якщо операція записується після операндів, це називається постфіксною формою, а якщо перед операндами — префіксною формою. Наприклад, вираз a-b*c у постфіксній формі виглядає як abc*-, а у префіксній — як -a*bc.

Шаблон бездужкової форми арифметичного виразу — це рядок, що складається з цифр $0$, $1$, $2$ і $3$. Тут $0$ позначає операнд, а решта цифр — операції. Значення цифри вказує на кількість операндів, необхідних для виконання відповідної операції.

Шаблон може бути як постфіксним, так і префіксним.

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