# Mermaid

Time limit: 0.03s Memory limit: 128MB Input: Output:

The title of the problem has as much to do with the statement as Denise's lyrics have to do with Marius's (for those who know).

On a $0$-indexed binary string $S$ of length $N$, you can apply the following operation any number of times:

• Choose an index $i$ ($0 \leq i < N - 1$) such that $S_i = S_{i+1}$ and remove $S_i$ and $S_{i+1}$ from $S$.

After this operation, we get the string $S_{0}\dots S_{i-1}S_{i+2}\dots S_{N-1}$.

Given a positive integer $N$, Conte the Swedish asks you to find the number of binary strings of length $N$ that can become empty after applying the operation above on them any number of times. Since this number can be very large, calculate it modulo $10^9 + 9$.

## Input data

The only line of the input will contain the number $N$.

## Output data

Output a single number, the number of binary strings of length $N$ that can become empty after applying the operation any number of times.

## Constraints and clarifications

• $1 \leq N \leq 2 \cdot 10^5$
• This problem was also given at Prosoft@NT 2024 — there, the subtasks were graded with $7$, $25$, $41$ and $27$ points.
# Points Constraints
1 3 $1 \leq N \leq 6$
2 11 $1 \leq N \leq 16$
3 38 $1 \leq N \leq 1 \ 000$

## Example

stdin

4


stdout

6


### Explanation

The $6$ strings are $1111$, $0000$, $1100$, $0011$, $0110$, $1001$.