Congratulations on finding the easy problem of this contest!
Given a sequence $\{a_0, a_1, \cdots, a_{n - 1}\}$ consisting only of $0$ and $1$. Find the number of sequences $\{b_0, b_1, \cdots, b_{m - 1}\}$ consisting only of $0$ and $1$ with length $m$ between $1$ and $n$ (inclusive), such that for any $0 \le p \le n - m$, the sum $\sum_{k = 0} ^ {m - 1}{a_{p + k} \wedge b_k}$ is even. Output the answer modulo $10^9+7$.
Input
A single string of $0$s and $1$s representing the sequence $a$, where the $k$-th character from the left represents $a_k$. It is guaranteed that $1 \le |a| \le 50000$.
Output
A single integer representing the number of sequences $b$ modulo $10^9+7$.
Examples
Input 1
00101110101110101011
Output 1
699063
Input 2
00001100100101110011110011100010011010101011001010
Output 2
932640914
Subtasks
Subtask 1 (1 point)
$n \leq 20$
Subtask 2 (1 point)
$n \leq 100$
Subtask 3 (2 points)
$n \leq 5\,000$
Subtask 4 (3 points)
No additional constraints.