問題一覧 > 通常問題

No.533 Mysterious Stairs

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 281
作問者 : takeya_okinotakeya_okino / テスター : maimai
2 ProblemId : 1755 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-06-25 00:23:02

問題文

赳也君は本日、ある雑居ビルの5Fで面接があります。運動不足解消の為、階段を使って面接会場まで向かいます。階段数はちょうどN stepあります。1回のjumpで1 or 2 or 3 step登れます。雑居ビル全体に奇妙なオーラが流れていて（もしくは面接への緊張感等の心理的理由から）、同じstep数のjumpを連続して行う事は出来ません。

赳也君の面接会場までのjumpの仕方は何通りあるでしょうか。答えが非常に大きくなる場合があるので、10^9+7で割った余りを求めなさい。

入力

N

1行目に面接会場までのstep数Nが与えられます。1≦N≦1000000

出力

ちょうどN stepするjumpのしかたが何通りあるかを出力してください。最後に改行してください。

サンプル

サンプル1
入力
2
出力
1

1回のjumpで2 stepする方法しかありません。1step+1stepという連続した同step数のjumpは行う事が出来ません。

サンプル2
入力
4
出力
3

(1,2,1),(3,1),(1,3)の3通りです。

サンプル3
入力
49993
出力
407466683

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