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 00-indexed binary string SS of length NN, you can apply the following operation any number of times:

  • Choose an index ii (0i<N10 \leq i < N - 1) such that Si=Si+1S_i = S_{i+1} and remove SiS_i and Si+1S_{i+1} from SS.

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

Task

Given a positive integer NN, Conte the Swedish asks you to find the number of binary strings of length NN 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 109+910^9 + 9.

Input data

The only line of the input will contain the number NN.

Output data

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

Constraints and clarifications

  • 1N21051 \leq N \leq 2 \cdot 10^5
  • This problem was also given at Prosoft@NT 2024 — there, the subtasks were graded with 77, 2525, 4141 and 2727 points.
# Points Constraints
1 3 1N61 \leq N \leq 6
2 11 1N161 \leq N \leq 16
3 38 1N1 0001 \leq N \leq 1 \ 000
4 48 No additional constraints.

Example

stdin

4

stdout

6

Explanation

The 66 strings are 11111111, 00000000, 11001100, 00110011, 01100110, 10011001.

Log in or sign up to be able to send submissions!