Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let $X_1,X_2,\dots,X_N$ be the digits of X from top to bottom. They satisfy all of the following:
• $1 \le X_i \le 9$ for all integers $1 \le i \le N$;
• $|X_i-X_{i+1}| \le 1$ for all integers $1 \le i \le N-1$.

Input

Input is given from Standard Input in the following format:
N

Output

Print the answer as an integer.

Constraints

• N is an integer.
• $2 \le N \le 10^6$

Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

见题面 Input 部分

见题面 Output 部分