Question
Avinash and the Mountain Stairs
Avinash is on an adventurous trek in the mountains. To reach the top of a cliff, he must climb a long staircase with n steps.
He starts at the 0-th step (ground). At each move, Avinash can:
-
Climb 1 step, or
-
Climb 2 steps, or
-
Climb 3 steps.
Two paths are considered different if the sequence of moves is different.
Your task is to determine the total number of distinct ways Avinash can reach the n-th step. Since the answer can be very large, return it modulo 109 + 7.
Input
The first line contains an integer n — the number of steps.
Output
Print the number of distinct ways to reach the nth step modulo 109 + 7.
Example
Input:
3
Output :
4
Explanation:
There are 4 ways for Avinash to climb to the 3rd stair:
0 → 1 → 2 → 3 (three single steps)
0 → 1 → 3 (one single step, one double step)
0 → 2 → 3 (one double step, one single step)
0 → 3 (one triple step)
3
Output :
4
Explanation:
There are 4 ways for Avinash to climb to the 3rd stair:
0 → 1 → 2 → 3 (three single steps)
0 → 1 → 3 (one single step, one double step)
0 → 2 → 3 (one double step, one single step)
0 → 3 (one triple step)