题目描述

给定一个整数 $N$，请计算满足以下所有条件的整数 $X$ 的数量，结果对 998244353 取模。

• $X$ 是一个 $N$ 位正整数。
• 设 $X_1,X_2,...,X_N$ 为 $X$ 从高位到低位的各个数字。它们满足以下所有条件：
  • 对于所有整数$1 ≤ i ≤ N$，有$1 ≤ X_i ≤ 9$；
  • 对于所有整数$1 ≤ i ≤ N-1$，有$|X_i-X_{i+1}| ≤ 1$。

输入格式

输入$N$。

输出格式

输出所求答案。

样例

4

203

2

25

1000000

248860093

样例解释

【样例1说明】
满足条件的4位整数包括 1111,1234,7878,6545 等。
【样例3说明】
请注意结果对998244353取模。

数据范围

$N$ 是整数，$2 ≤ N ≤ 10^6$。

来源

• AtCoder ABC242C