How many templates?
Arithmetic expressions can be represented in a bracket-free form. In this format, if the operator follows the operands, it is known as postfix notation; if the operator precedes the operands, it is called prefix notation. For instance, the expression a-b*c is written as abc*- in postfix notation and as -a*bc in prefix notation.
A template for a bracket-free arithmetic expression consists of a sequence using the digits 0, 1, 2, and 3. Here, 0 represents an operand, while the other digits denote operations. The value of the digit indicates the number of operands required for the operation.
The template can be in either postfix or prefix form.
Given the length of the template N, your task is to calculate the total number of valid prefix templates of length N that use only the symbols 0 and 3. Provide the result modulo 1000000009 (10^9+9).
Input
The input consists of a single line containing an integer N (0 ≤ N ≤ 1000).
Output
Output a single line with the answer to the problem.