9571: ABC242 —— C - 1111gal password
[Creator : ]
Description
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$.
- $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$
```
```
$N$
```
Output
Print the answer as an integer.
Constraints
- $N$ is an integer.
- $2 \le N \le 10^6$
- $2 \le N \le 10^6$
Sample 1 Input
4
Sample 1 Output
203
Some of the 44-digit integers satisfying the conditions are 1111,1234,7878,6545.
Sample 2 Input
2
Sample 2 Output
25
Sample 3 Input
1000000
Sample 3 Output
248860093