問題文

整数 $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$ で割った余りを求めることに注意してください。