URI Online Judge | 2986
# Not Everything is Strike Hard Version

**Timelimit: 1**

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 (10^{9} + 7).

Input Samples | Output Samples |

1 |
1 |

5 |
13 |

1000 |
509672692 |