A pier stairway has steps numbered 0 (the landing where you start) up to n (the deck you want to reach). Some steps are broken and cannot be landed on. On each move you step up either 1 or 2 steps, and you must never land on a broken step. Step 0 is guaranteed usable.
The condition of the steps is given as a binary string b of length n + 1, where b[i] is 1 if step i is broken and 0 if it is usable.
Count the number of distinct climbs from step 0 to step n that never land on a broken step. Print the count modulo 1000000007. If step n itself is broken, the answer is 0.
Line 1: the integer n.
Line 2: a binary string b of length n + 1; b[0] is always 0.
A single integer: the number of valid climbs, taken modulo 1000000007.
b has length exactly n + 1 and consists only of 0 and 1, with b[0] = 0.Example 1
Input
4 00000
Expected
5
Explanation
No step is broken, so climbing 4 steps with moves of 1 or 2 gives the usual 5 ways.
Example 2
Input
4 00100
Expected
1
Explanation
Step 2 is broken. The only valid climb is 0 -> 1 -> 3 -> 4, 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 →