1111gal 密码

题目描述

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

• $X$ 是 $N$ 位正整数。
• 设 $X_1,X_2,\dots,X_N$ 为 $X$ 从高位到低位的各位数字。它们满足:
  • 对所有整数 $1 \le i \le N$,有 $1 \le X_i \le 9$;
  • 对所有整数 $1 \le i \le N-1$,有 $|X_i-X_{i+1}| \le 1$。

输入格式

输入按以下格式从标准输入给出:

N

输出格式

输出答案(整数)。

样例

4

203

满足条件的 $4$ 位整数中,有 $1111$、$1234$、$7878$、$6545$ 等。

2

25

1000000

248860093

请务必输出对 $998244353$ 取模后的答案。

数据范围

• $N$ 是整数。
• $2 \le N \le 10^6$