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 $10^9+7$, since the answer could be very large.
### Constraints
- $1 \le n \le 10^5$.
### 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)$
