Home

Contest: Task: Related: TaskB TaskD

Score : $300$ points

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

Constraints

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

Input

Input is given from Standard Input in the following format:

$N$

Output

Print the answer as an integer.

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