题目描述

给定一个整数 $N$，找到满足以下所有条件的整数 $X$ 的数量（对 $998244353$ 取模）。

• $X$ 是一个 $N$ 位的正整数。
• 令 $X_1,X_2,\\dots,X_N$ 是 $X$ 的从高到低的位数。它们满足以下所有条件：
  • 对于所有整数 $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$ 取模后计算结果。