P2106 Sam Numbers

Xiao Z recently discovered a very interesting type of number, which he calls a Sam number. Sam numbers have the following property: the difference between any two adjacent digits does not exceed $2$. Xiao Z also classifies Sam numbers by their number of digits. He calls a $k$-digit Sam number a $k$-order Sam number. Unfortunately, Xiao Z cannot figure out how many $k$-order Sam numbers there are, so he turns to you for help. The answer should be taken modulo $10^9 + 7$.

The input contains a single integer $k$, as described above.

Output a single integer $ans$, the number of $k$-order Sam numbers. The answer should be taken modulo $10^9 + 7$.

Constraints: - For $30\%$ of the testdata, $1 \le k \le 10^6$. - For $60\%$ of the testdata, $1 \le k \le 10^{12}$. - For $100\%$ of the testdata, $1 \le k \le 10^{18}$. Translated by ChatGPT 5