4265: 满足以下所有条件的整数 X 的数量

内存限制：1024 MB 时间限制：2.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

# 1111gal password ## 题目描述 给定一个整数 $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$。

输出

## 输出格式 输出所求答案。

样例输入 复制 

4

样例输出 复制 

203

提示

## 输入输出样例 ### 输入样例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
提交提交记录统计露一手!