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.

# | Points | Constraints |
---|---|---|

1 | 3 | $1 \leq N \leq 6$ |

2 | 11 | $1 \leq N \leq 16$ |

3 | 38 | $1 \leq N \leq 1 \ 000$ |

4 | 48 | No additional constraints. |

## Example

`stdin`

```
4
```

`stdout`

```
6
```

### Explanation

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