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.
Input format
Line 1: the integer n.
Line 2: a binary string b of length n + 1; b[0] is always 0.
Output format
A single integer: the number of valid climbs, taken modulo 1000000007.
Constraints
- 1 <= n <= 20
bhas length exactly n + 1 and consists only of0and1, withb[0] = 0.