Дан массив $\{a_0, a_1, \cdots, a_{n - 1}\}$, состоящий только из $0$ и $1$. Найдите количество последовательностей $\{b_0, b_1, \cdots, b_{m - 1}\}$ длины от $1$ до $n$, состоящих только из $0$ и $1$, таких что для любого $0 \le p \le n - m$ выполняется условие: $\sum_{k = 0} ^ {m - 1}{a_{p + k} \wedge b_k}$ является четным числом.
Ответ выведите по модулю $1\,000\,000\,007$.
Входные данные
Одна строка, содержащая 01-строку, представляющую массив $a$, где $k$-й символ слева направо соответствует $a_k$.
Выходные данные
Одно целое число — количество последовательностей $b$ по модулю $1\,000\,000\,007$.
Примеры
Пример 1
00101110101110101011
Вывод 1
699063
Пример 2
00001100100101110011110011100010011010101011001010
Вывод 2
932640914
Ограничения
Ограничения для каждой группы тестов приведены в таблице ниже:
| Номер теста | $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 |
Для всех тестов $1 \le n \le 50000$, входная строка состоит только из символов $0$ и $1$.