给定一个仅由 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$ 取模的值。

样例一

input

00101110101110101011

output

699063

样例二

input

00001100100101110011110011100010011010101011001010

output

932640914

限制与约定

每组测试数据的限制与约定如下所示：

对于全部数据$1 \le n \le 50000$，输入数据中的串是一个01串。