A lighthouse keeper climbs a vertical ladder to the lamp gallery. The ladder has n rungs above the floor, and on each move the keeper steps up either exactly 1 rung or exactly 2 rungs. Two climbs are considered different if the ordered sequence of move sizes differs.
Count how many distinct climbs reach exactly rung n, starting from the floor (rung 0). Because the count can be enormous, print it modulo 1000000007.
Input format
A single line containing the integer n.
Output format
A single integer: the number of distinct climbs, taken modulo 1000000007.
Constraints
- 0 <= n <= 100000
- An empty climb (making no move) is the only way to reach rung 0, so the answer for n = 0 is 1.