Not Everything is Strike Hard Version
By Roger Eliodoro Condras, UFSC-ARA 
Brazil
By Roger Eliodoro Condras, UFSC-ARA Brazil
Once, while studying for the Porgramption Marathon, Tobias and I come across an interesting problem, I hope you enjoy it too.
There is a staircase with N steps. You can choose to go down 1, 2, or 3 steps at a time with each move. How many different ways could you go down this stair with N steps?
A single integer N (1 ≤ N ≤ 1,000,000), the number of stairs in the ladder.
A single integer, the number combinations of different ways down the ladder. The answer may be a little big, so print the rest of the division by our favorite cousin (109 + 7).
| Input Samples | Output Samples |
|
1 |
1 |
|
5 |
13 |
|
1000 |
509672692 |