Score : $300$ points

问题描述

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

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Given an integer $N$, find the number of integers $X$ that satisfy all of the following conditions, modulo $998244353$.

• $X$ is an $N$-digit positive integer.
• Let $X_1,X_2,\dots,X_N$ be the digits of $X$ from top to bottom. They satisfy all of the following:
  • $1 \le X_i \le 9$ for all integers $1 \le i \le N$;
  • $|X_i-X_{i+1}| \le 1$ for all integers $1 \le i \le N-1$.

Constraints

• $N$ is an integer.
• $2 \le N \le 10^6$

Input

Input is given from Standard Input in the following format:

$N$

Output

Print the answer as an integer.

Sample Input 1

4

Sample Output 1

203

Some of the $4$-digit integers satisfying the conditions are $1111,1234,7878,6545$.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo $998244353$.

update @ 2024/3/10 10:25:14