No.314 ケンケンパ

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 397
作問者 : roiti46roiti46
22 ProblemId : 882 / 出題時の順位表

Note

この問題はAdvent Calendar Contest Advent Calendar 2015の7日目の問題として作られました。

問題文

たろうくんはケンケンパが好きです。
ケンケンパとは片足跳びの「ケン」と両足着地の「パ」とを繰り返す遊びです。
今、たろうくんは長さNの新しいケンケンパコースを作ろうと考えています。
楽しいケンケンパコースにするために、次の2つの条件を守ってコースを作らないといけません。

1. 「ケン」は3回以上続いてはいけない
2. 「パ」は「ケン」のあとにしか置けない

たろうくんは何通りのコースが作れるのか気になっていますが、幼稚園児なので計算がうまくできません。
そこで、たろうくんの代わりに何通りのコースが作れるかを求めてあげてください。
ただし、答えは非常に大きくなる可能性があるので109+7で割った余りを出力してください。

入力

$N$

Nは1以上106以下の整数です

出力

何通りのコースが作れるか、109+7で割った余りを出力してください

サンプル

サンプル1
入力
3
出力
2

「ケンケンパ」と「ケンパケン」の2通りがありえます。

サンプル2
入力
4
出力
3

「ケンケンパケン」と「ケンパケンパ」と「ケンパケンケン」の3通りがありえます。

サンプル3
入力
100
出力
831891005

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。