题目描述

整数 $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$

输出格式

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

题目大意

给出整数 $N$，请求出长度为 $N$ 的满足以下条件的正整数 $X$ 的情况数，除以 $998244353$ 的余数。

1.$X$长度为 $N$。

2.若 $X$ 的各个数位表示为 $x_1,x_2,……x_n$，则它们满足以下条件：

• 对于所有正整数 $i$（$1 \le\ i \le\ N$），$1 \le\ x_i \le\ 9$

• 对于所有正整数 $i$（$1 \le\ i < N$），$|x_{i+1}-x_i| \le\ 1$

4

203

2

25

1000000

248860093

提示

制約

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

Sample Explanation 1

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

Sample Explanation 3

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