当前没有测试数据。

C - 1111gal密码

得分：$300$ 分

问题描述

给定一个整数 $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$

输出

以整数形式输出答案。

4

203

满足条件的一些 $4$ 位整数有 $1111,1234,7878,6545$。

2

25

1000000

248860093

请确保将计数结果取模 $998244353$。