Given a sequence $\{a_0, a_1, \cdots, a_{n - 1}\}$ consisting only of 0s and 1s, find the number of sequences $\{b_0, b_1, \cdots, b_{m - 1}\}$ of length $m$ (where $1 \le m \le n$) consisting only of 0s and 1s, such that for all $0 \le p \le n - m$, the sum $\sum_{k = 0} ^ {m - 1}{a_{p + k} \wedge b_k}$ is even.
The answer should be taken modulo $1\,000\,000\,007$.
Input
A single 01 string representing the sequence $a$, where the $k$-th character from the left represents $a_k$.
Output
A single integer representing the number of sequences $b$ modulo $1\,000\,000\,007$.
Examples
Input 1
00101110101110101011
Output 1
699063
Input 2
00001100100101110011110011100010011010101011001010
Output 2
932640914
Constraints
The constraints for each test case are as follows:
| Test Case ID | $n$ |
|---|---|
| 1 | $n \le 20$ |
| 2 | |
| 3 | $n \le 100$ |
| 4 | |
| 5 | |
| 6 | |
| 7 | $n \le 5000$ |
| 8 | |
| 9 | |
| 10 | |
| 11 | |
| 12 | |
| 13 | $n \le 50000$ |
| 14 | |
| 15 | |
| 16 | |
| 17 | |
| 18 | |
| 19 | |
| 20 |
For all test cases, $1 \le n \le 50000$, and the input is a 01 string.