UOJ Logo Universal Online Judge

UOJ

#293. 【集训队互测2017】序列计数

统计

给定一个仅由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}$均为偶数。

答案对1000000007取模。

输入格式

一行一个01串,表示数列$a$,从左到右的第$k$个字符表示$a_k$。

输出格式

一行一个整数表示数列$b$的个数对1000000007取模的值。

样例一

input

00101110101110101011

output

699063

样例二

input

00001100100101110011110011100010011010101011001010

output

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串。

时间限制:$1\texttt{s}$

空间限制:$1024\texttt{MB}$

下载

样例数据及题解下载

来源

matthew99