Description

In Xiao Z’s basement, there are $n$ small blocks placed side by side (Xiao Z is a hardcore MC fan who likes decorating his basement with small blocks), and each block is different (Xiao Z likes things to be unique), such as grass block, marble, obsidian, etc.

Xiao Z likes to arrange these small blocks in a special order, for example: grass block, marble, obsidian. One day, Xiao D helped Xiao Z tidy up the basement, but the not-so-bright Xiao D forgot the exact positions after moving all the blocks out. With only a vague memory, Xiao D might place the block originally at position $i$ to any of positions $i-1$, $i$, or $i+1$ (of course, the $1$st cannot be placed at position $0$, and the $n$th cannot be placed at position $n+1$), for example (corresponding to the example above): marble, grass block, obsidian.

Xiao Z is a generous person. He wants to compute how many possible final arrangements Xiao D could make, and he will not hold Xiao D responsible. Since he is also not very bright, if the answer is large, he only wants to see the last $8$ digits (do not show leading zeros).

Count the number of permutations $\{p_n\}$ of $1 \sim n$ that satisfy $|p_i-i| \le 1$, and take the answer modulo $10^8$.

Input Format

One line, a positive integer $n$, meaning there are $n$ small blocks in Xiao Z’s basement.

Output Format

One line, a positive integer, the number of possible final arrangements Xiao D could make. Output only the last $8$ digits, and do not output leading zeros.

3

3

987

223731

Hint

[Sample Explanation 1]

Continuing the example in the statement, there are $3$ possibilities: (grass block, marble, obsidian), (marble, grass block, obsidian), (grass block, obsidian, marble).

[Constraints]

For $30\%$ of the testdata, $n \le 10^6$.

For $50\%$ of the testdata, $n \le 10^{16}$.

For $100\%$ of the testdata, $1 \le n \le 10^{1000}$.

Translated by ChatGPT 5