問題文
Daylight君はN日間の朝食の献立表を作ることにしました。献立表には、N日それぞれについて、その日に食べる朝食のメニューを記載します。
朝食のメニューは以下の4種類のパンから1種類が選ばれます。
- ノーマルパン
- カレーパン
- 小豆パン
- 小豆カレーパン
Daylight君は同じ味のパンを連続で食べると飽きてしまいます。そこで、献立には以下の制約を設けることにしました。
- カレーが入っているパン(名称にカレーを含むパン)を食べた翌日は、カレーが入っているパンを食べない。
- 小豆が入っているパン(名称に小豆を含むパン)を食べた翌日と翌々日は、小豆が入っているパンを食べない。
N日それぞれについて、4種類のパンから1種類を選んで作られた献立表は4N通り存在しますが、このうち上記の制約を満たす献立表が何通り存在するか、998244353で割った余りを出力してください。
制約
- 1≤N≤1018
入力
入力はすべて整数です。
出力
問題文中の制約を満たす献立表が何通り存在するか、998244353で割った余りを出力してください。
サンプル
制約を満たす献立として以下のように9通りが存在します。
- 初日にノーマルパンを選んだ場合、二日目は4種類のパンすべてを選ぶことができます。
- 初日にカレーパンを選んだ場合、二日目はノーマルパンか小豆パンの2種類のみ選ぶことができます。
- 初日に小豆パンを選んだ場合、二日目はノーマルパンかカレーパンの2種類のみ選ぶことができます。
- 初日に小豆カレーパンを選んだ場合、二日目はノーマルパンの1種類のみ選ぶことができます。