C - 1111gal password Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数 N が与えられるので、以下の条件を全て満たす整数 X の個数を 998244353 で割った余りを求めてください。

  • N 桁の正整数である。
  • X の各桁を上の位から順に X_1,X_2,\dots,X_N とする。このとき以下の条件を全て満たす。
    • 全ての整数 1 \le i \le N に対して、 1 \le X_i \le 9
    • 全ての整数 1 \le i \le N-1 に対して、 |X_i-X_{i+1}| \le 1

制約

  • N は整数
  • 2 \le N \le 10^6

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを整数として出力せよ。

入力例 1

4

出力例 1

203

4 桁の整数として、例えば 1111,1234,7878,6545 が問題文中の条件を満たします。

入力例 2

2

出力例 2

25

入力例 3

1000000

出力例 3

248860093

998244353 で割った余りを求めることに注意してください。

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.