問題文

Daylight君は$N$日間の朝食の献立表を作ることにしました。献立表には、$N$日それぞれについて、その日に食べる朝食のメニューを記載します。 朝食のメニューは以下の$4$種類のパンから$1$種類が選ばれます。

• ノーマルパン
• カレーパン
• 小豆パン
• 小豆カレーパン

Daylight君は同じ味のパンを連続で食べると飽きてしまいます。そこで、献立には以下の制約を設けることにしました。

• カレーが入っているパン(名称にカレーを含むパン)を食べた翌日は、カレーが入っているパンを食べない。
• 小豆が入っているパン(名称に小豆を含むパン)を食べた翌日と翌々日は、小豆が入っているパンを食べない。

$N$日それぞれについて、$4$種類のパンから$1$種類を選んで作られた献立表は$4^N$通り存在しますが、このうち上記の制約を満たす献立表が何通り存在するか、$998244353$で割った余りを出力してください。

制約

• $1 \leq N \leq 10^{18}$

入力

入力はすべて整数です。

N

出力

問題文中の制約を満たす献立表が何通り存在するか、$998244353$で割った余りを出力してください。

サンプル

2

9

制約を満たす献立として以下のように$9$通りが存在します。

• 初日にノーマルパンを選んだ場合、二日目は$4$種類のパンすべてを選ぶことができます。
• 初日にカレーパンを選んだ場合、二日目はノーマルパンか小豆パンの$2$種類のみ選ぶことができます。
• 初日に小豆パンを選んだ場合、二日目はノーマルパンかカレーパンの$2$種類のみ選ぶことができます。
• 初日に小豆カレーパンを選んだ場合、二日目はノーマルパンの$1$種類のみ選ぶことができます。

3

20