恭喜你找到了本场比赛的签到题！
给定一个仅由 $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}$均为偶数，答案对 $10^9+7$ 取模。
输入格式
一行一个01串，表示数列$a$，从左到右的第$k$个字符表示$a_k$。保证 $1 \le |a| \le 50000$。
输出格式
一行一个整数表示数列$b$的个数对 $10^9+7$ 取模的值。
样例一
input
00101110101110101011
output
699063
input
00001100100101110011110011100010011010101011001010
output
932640914
子任务
子任务一（1 分）
$n \leq 20$
子任务二（1 分）
$n \leq 100$
子任务三（2 分）
$n \leq 5\,000$
子任务四（3 分）
没有额外的限制。