题目描述

给定一个整数 $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$。

输出格式

输出所求答案。

输入输出样例 #1

输入 #1

4

输出 #1

203

输入输出样例 #2

输入 #2

2

输出 #2

25

输入输出样例 #3

输入 #3

1000000

输出 #3

248860093

说明/提示

样例 1 解释

满足条件的 $4$ 位整数包括 $1111,1234,7878,6545$ 等。

样例 3 解释

请注意结果对 $998244353$ 取模。

数据范围

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