A ropeway inspector ascends a staircase of n steps. On each move the inspector goes up exactly 1, 2, or 3 steps. Two ascents differ if the ordered sequence of move sizes differs.
Count the number of distinct ascents that land exactly on step n, starting from step 0. Print the count modulo 1000000007.
A single line containing the integer n.
A single integer: the number of distinct ascents, taken modulo 1000000007.
Example 1
Input
4
Expected
7
Explanation
Reaching step 4 with steps of size 1/2/3 can be done 7 ways (e.g. 1+3, 3+1, 2+2, 1+1+2, and so on).
Example 2
Input
0
Expected
1
Explanation
The only ascent to step 0 is the empty one, so the answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →