Marisa must climb n steps to reach Hakurei Shrine at the top of the mountain. If she climbs either 1 step, 2 steps, or 3 steps at a time, in how many ways can Marisa reach the shrine?
### Input
- The first line contains an integer n.
### Output
- Print the number of ways, modulo 109+7, since the answer could be very large.
### Constraints
- 1≤n≤105.
### Example
Input:
4
Output:
7
#### Note: There are 7 ways for Marisa to reach the shrine: (1,1,2),(1,2,1),(2,1,1),(1,3),(3,1),(2,2),(1,1,1,1)
