题目描述

小明学校花园有一条路，可以看作是 $\red{3}$ 行 $\red{n}$ 列的矩阵。校长打算把它铺上 $\red{1 \times 1,2 \times 2}$ 或 $\red{3 \times 3}$ 的正方形地砖。地砖不能切割，路必须铺满，但地砖又不能铺出这条路。现在校长想知道有多少种方案是符合要求的。

输入格式

一行一个正整数 $\red{n}$。

输出格式

一行一个正整数，为答案。因为答案可能很大，所以要输出答案对 $\red{998244353}$ 取模的值。

样例

输入样例1

2

输出样例1

3

输入样例2

4

输出样例2

13

提示

$\red{n=2}$ 时，有以下 $\red{3}$ 种铺法：

$\red{1 \le n \le 10^5}$