問題一覧 > 通常問題

No.533 Mysterious Stairs

レベル : / AI推定難易度 : 400 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 289
作問者 : takeya_okino / テスター : mai
お気に入りにしたユーザー ProblemId : 1755 / 自分の提出
問題文最終更新日: 2026-06-26 06:06:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 167 (順位表) の他の問題:

Problem Statement

Today, Takeya has an interview on the 5th floor of a multi-tenant building. To make up for his lack of exercise, he will use the stairs to get to the interview venue. The staircase has exactly N steps. In one jump, he can climb 1 or 2 or 3 steps. A strange aura pervades the entire building (or perhaps it is due to psychological reasons such as nervousness about the interview), so he cannot make jumps of the same number of steps consecutively.

How many ways can Takeya jump to reach the interview venue? Since the answer can be very large, find the remainder when divided by 10^9+7.

Input

N

The first line gives the number of steps N to the interview venue. 1≦N≦1000000

Output

Output the number of ways to jump exactly N steps. Print a newline at the end.

Sample

Sample 1
Input
2
Output
1

The only way is to climb 2 steps in one jump. The consecutive jumps of the same number of steps, 1step+1step, cannot be made.

Sample 2
Input
4
Output
3

There are 3 ways: (1,2,1),(3,1),(1,3).

Sample 3
Input
49993
Output
407466683

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