P2100 Messy Basement

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

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

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.

[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