题目描述

给出整数 $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$。

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

输出格式

方案数。

4

203

2

25

1000000

248860093