Attempt

Please login to see your submissions result.

Problem

Mary has to climb ~N~ steps to reach the Hakurei Shrine on the mountain. If she can take ~1~, ~2~, or ~3~ steps at a time, how many ways can she reach the shrine?

Input

Single line contain a positive integer ~N~.

Output

Print a single positive integer as the result of the problem. Since the answer can be very large, print the result modulo ~10^9+7~.

Constraints

~1 \leq N \leq 10^5~.

Sample

Explanation

In the first sample test, there are 7 ways for Mary to reach the shrine: ~(1, 1, 2), (1, 2, 1), (2, 1, 1), (1, 3), (3, 1), (2, 2), (1, 1, 1)~.