给定一个整数 $N$，请你求满足以下所有条件的整数 $X$ 的个数，并将结果对 $998244353$ 取模后输出。

• $X$ 是一个 $N$ 位的正整数。
• 设 $X$ 的各位数字从高到低依次为 $X_1, X_2, \dots, X_N$，则需满足以下所有条件：
  • 对于所有 $1 \leq i \leq N$，都有 $1 \leq X_i \leq 9$。
  • 对于所有 $1 \leq i \leq N-1$，都有 $|X_i - X_{i+1}| \leq 1$。

输入格式

输入为以下格式，从标准输入读取。

$N$

输出格式

请输出满足条件的整数个数，对 $998244353$ 取模后的结果。

4

203

2

25

1000000

248860093

说明/提示

限制条件

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

样例解释 1

作为 $4$ 位整数，例如 $1111, 1234, 7878, 6545$ 都满足题目中的条件。