Скільки шаблонів?
Арифметичні вирази можна записувати у бездужковій формі. Якщо операція записується після операндів, це називається постфіксною формою, а якщо перед операндами — префіксною формою. Наприклад, вираз a-b*c у постфіксній формі виглядає як abc*-, а у префіксній — як -a*bc.
Шаблон бездужкової форми арифметичного виразу — це рядок, що складається з цифр 0, 1, 2 і 3. Тут 0 позначає операнд, а решта цифр — операції. Значення цифри вказує на кількість операндів, необхідних для виконання відповідної операції.
Шаблон може бути як постфіксним, так і префіксним.
Для заданої довжини шаблону N потрібно визначити загальну кількість коректних префіксних шаблонів довжини N, які можуть містити лише символи 0 і 3. Відповідь слід подати за модулем 1000000009 (10^9+9).
Вхідні дані
У єдиному рядку вхідного файлу задано ціле число N (0 ≤ N ≤ 1000).
Вихідні дані
У єдиному рядку виведіть відповідь на задачу.