Сколько шаблонов?
Как известно, арифметические выражения можно записывать в так называемой бесскобочной форме. При этом, если операция записывается после операндов, то мы имеем постфиксную запись, а если перед операндами, то мы имеем префиксную запись. Например, выражение a-b*c в первом случае будет иметь вид abc*- , а во втором случае вид -a*bc.
Под шаблоном бесскобочной формы арифметического выражения будем понимать строку, составленную из цифр 0, 1, 2 и 3. Где 0 будет означать операнд, а остальные цифры — операции. Величина цифры определяет количество операндов, необходимое для выполнения соответствующей операциии.
Шаблон может быть как постфиксным, так и префиксным.
По заданной длине шаблона N определить общее количество корректных префиксных шаблонов длины N, в которых могут использоваться только символы 0 и 3. Ответ выдать по модулю 1000000009 (10^9+9).
Входные данные
В единственной строке входного файла целое число N (0 ≤ N ≤ 1000).
Выходные данные
В единственной строке – ответ задачи.