题目描述

给出整数 $N$，请求出长度为 $N$ 的满足以下条件的正整数 $X$ 的情况数，除以 $998244353$ 的余数。

1. $X$长度为 $N$。
2. 若 $X$ 的各个数位表示为 $x_1,x_2,……x_n$，则它们满足以下条件：

• 对于所有正整数 $i$（$1 \le\ i \le\ N$），$1 \le\ x_i \le\ 9$
• 对于所有正整数 $i$（$1 \le\ i < N$），$|x_{i+1}-x_i| \le\ 1$

输入格式

输入一个整数 $N$

输出格式

输出方案数

4

203

2

25

1000000

248860093

提示

• $2\ \le\ N\ \le\ 10^6$