URI Online Judge | 2986

Not Everything is Strike Hard Version

By Roger Eliodoro Condras, UFSC-ARA BR Brazil

Timelimit: 1

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?

Input

A single integer N (1 ≤ N ≤ 1,000,000), the number of stairs in the ladder.

Output

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