AT_abc242_c [ABC242C] 1111gal password

题目描述

给定一个整数 $N$，请你求满足以下所有条件的整数 $X$ 的个数，并将结果对 $998244353$ 取模后输出。

• $X$ 是一个 $N$ 位的正整数。
• 设 $X$ 的各位数字从高到低依次为 $X_1, X_2, \dots, X_N$，则需满足以下所有条件：
  • 对于所有 $1 \leq i \leq N$，都有 $1 \leq X_i \leq 9$。
  • 对于所有 $1 \leq i \leq N-1$，都有 $|X_i - X_{i+1}| \leq 1$。

输入格式

输入为以下格式，从标准输入读取。

$N$

输出格式

请输出满足条件的整数个数，对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

4

输出 #1

203

输入输出样例 #2

输入 #2

2

输出 #2

25

输入输出样例 #3

输入 #3

1000000

输出 #3

248860093

说明/提示

限制条件

• $N$ 是整数。
• $2 \leq N \leq 10^6$。

样例解释 1

作为 $4$ 位整数，例如 $1111, 1234, 7878, 6545$ 都满足题目中的条件。

样例解释 3

请注意，答案需要对 $998244353$ 取模。

由 ChatGPT 4.1 翻译