4265: 1111gal password
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
# 1111gal password
### 内存
1024MB
### 时间
2S
## 题目描述
给定一个整数 $N$,请计算满足以下所有条件的整数 $X$ 的数量,结果对 998244353 取模。
- $X$ 是一个 $N$ 位正整数。
- 设 $X_1,X_2,...,X_N$ 为 $X$ 从高位到低位的各个数字。它们满足以下所有条件:
- 对于所有整数$1 ≤ i ≤ N$,有$1 ≤ X_i ≤ 9$;
- 对于所有整数$1 ≤ i ≤ N-1$,有$|X_i-X_{i+1}| ≤ 1$。
## 输入格式
输入$N$。
## 输出格式
输出所求答案。
## 输入输出样例
### 输入样例1
```
4
```
### 输出样例1
```
203
```
### 输入样例2
```
2
```
### 输出样例2
```
25
```
### 输入样例3
```
1000000
```
### 输出样例3
```
248860093
```
## 数据范围与提示
【样例1说明】
满足条件的4位整数包括 1111,1234,7878,6545 等。
【样例3说明】
请注意结果对998244353取模。
【数据范围】
$N$ 是整数,$2 ≤ N ≤ 10^6$。
## 题目来源
ABC242C