問題一覧 > 通常問題

No.314 ケンケンパ

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 575
作問者 : roiti46roiti46
27 ProblemId : 882 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-12-05 19:22:03

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。