小学要开晚会了，法珞拿出了 $n$ 个凳子摆成一排，有 $n$ 个小朋友依次过来入座。

小朋友们都喜欢宽敞的地方，所以他们入座的规则是：

1. 优先选相邻两个座位都没有人的座位（有不止一个的话就随便选，下同）。
2. 如果没有的话优先选相邻两个座位里只有一个人的座位。
3. 如果也没有的话就随便选。

求这 $n$ 个小朋友最后入座情况的方案数对 $998244353$ 取模的结果。

定义两种入座情况不同当且仅当存在某个小朋友在两种方案中坐在了不同的凳子上。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数表示方案数对 $998244353$ 取模的结果。

样例一

input

4

output

8

explanation

对于样例一，八种情况如图所示

样例二

input

9

output

11232

样例三

input

2333

output

98954774

限制与约定

对于 $30\texttt{%}$ 的数据，$1 \le n \le 20$。

对于 $60\texttt{%}$ 的数据，$1 \le n \le 2501$。

对于 $80\texttt{%}$ 的数据，$1 \le n \le 152501$。

对于 $100\texttt{%}$ 的数据，$1 \le n \le 10^7$。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载