1111gal password

题目描述

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

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

输入格式

输入从标准输入按以下格式给出： $N$

输出格式

输出答案（整数）。

4

203

2

25

1000000

248860093

提示

$N$ 是一个整数。 $2 \le N \le 10^6$满足条件的一些 $4$ 位整数有 $1111,1234,7878,6545$.
注意对 $998244353$ 取模。

标签: AtCoder|abc242C

来源

AtCoder|abc242C