Making a plan of breakfast

2 secs 1024 MB
Daylight

問題文


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

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

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

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

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

制約


入力


入力はすべて整数です。

N

出力


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

サンプル


入力1
2
出力1
9

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

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

提出


Go (1.14)