0 と 1 のみからなる数列 $\{a_0, a_1, \cdots, a_{n - 1}\}$ が与えられる。長さが $1$ 以上 $n$ 以下である 0 と 1 のみの数列 $\{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$ で割った余りを出力せよ。
入力
数列 $a$ を表す 01 文字列が 1 行で与えられる。左から $k$ 番目の文字が $a_k$ を表す。
出力
数列 $b$ の個数を $1\,000\,000\,007$ で割った余りを 1 行で出力せよ。
入出力例
入力 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 文字列である。