该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

输入

4

输出

203

样例 2

输入

2

输出

25

样例 3

输入

1000000

输出

248860093

说明/提示

限制条件

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

样例解释 1

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

样例解释 3

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

由 ChatGPT 4.1 翻译