A ropeway inspector ascends a staircase of n steps. On each move the inspector goes up exactly 1, 2, or 3 steps. Two ascents differ if the ordered sequence of move sizes differs.
Count the number of distinct ascents that land exactly on step n, starting from step 0. Print the count modulo 1000000007.
Input format
A single line containing the integer n.
Output format
A single integer: the number of distinct ascents, taken modulo 1000000007.
Constraints
- 0 <= n <= 100000
- The empty ascent is the only way to reach step 0, so the answer for n = 0 is 1.