Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 300300 points
Problem Statement
Given an integer NN, find the number of integers XX that satisfy all of the following conditions, modulo 998244353998244353.
-
XX is an NN-digit positive integer.
-
Let X_1,X_2,\dots,X_NX1,X2,…,XN be the digits of XX from top to bottom. They satisfy all of the following:
-
1 \le X_i \le 91≤Xi≤9 for all integers 1 \le i \le N1≤i≤N;
-
|X_i-X_{i+1}| \le 1∣Xi−Xi+1∣≤1 for all integers 1 \le i \le N-11≤i≤N−1.
Constraints
-
NN is an integer.
-
2 \le N \le 10^62≤N≤106
Input
Input is given from Standard Input in the following format:
NN
Output
Print the answer as an integer.