Problem Description

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

Input Format

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

Output Format

Output a single integer $ans$, the number of $k$-order Sam numbers.

The answer should be taken modulo $10^9 + 7$.

4

867

Hint

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