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.
A single line containing the integer n.
A single integer: the number of distinct climbs, taken modulo 1000000007.
Example 1
Input
4
Expected
5
Explanation
The climbs to rung 4 are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, and 2+2, giving 5 distinct climbs.
Example 2
Input
0
Expected
1
Explanation
With no rungs to climb, the only climb is the empty one, so the answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →