給定一個僅由 0 和 1 組成的數列 $\{a_0, a_1, \cdots, a_{n - 1}\}$。求有多少個僅由 0 和 1 組成的長度在 $1$ 到 $n$ 之間的數列 $\{b_0, b_1, \cdots, b_{m - 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$，輸入資料中的串是一個 01 串。