No.314 ケンケンパ

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 148
作問者 : roiti46

14 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

提出ページヘ