Mermaid

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}$.

Task

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.

Example

stdin

4

stdout

6

Explanation

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