You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面描述

众所周知, wjj 是 0, 所以他讨厌没有 0 的数字, 他也讨厌相邻两数差值很小的数字, 他想知道, 所有的 $n$ 位数中, 有多少个他讨厌的数字.

给你一个整数 $n$, 我们要求出满足如下条件的数字的个数.

• 这是一个十进制 $n$ 位数
• 这个 $n$ 位数中没有 0, 如果有 0, 则不讨厌
• 所有的相邻两位差的绝对值 小于等于 1

注意: 这个数字可能很大, 我们需要对 998244353 求模.

输入格式

第一行输入一个整数 $n$

输出格式

输出一个整数表示答案

样例 #1

样例输入 #1

3

样例输出 #1

71

样例 #2

样例输入 #2

2

样例输出 #2

25

样例 #3

样例输入 #3

100

样例输出 #3

546005177

提示

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