#1917. 序列计数

    ID: 1917 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>CTT赛事:contest1971来源:qoj.ac数据:公开样例动态规划数学

序列计数

序列计数

题目描述

标题: 序列计数 - Problem - QOJ.ac

#10352. 序列计数

Statistics

The problem was used in the following contests:

给定一个仅由 0 和 1 组成的数列{a0,a1,⋯,an−1}。求有多少个仅有0和1组成的长度在 1 到 n 之间的数列 {b0,b1,⋯,bm−1},使得对于任意 0≤p≤n−m,∑k=0m−1ap+k∧bk均为偶数。

答案对 1000000007 取模。

输入格式

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

输出格式

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

样例一

input

00101110101110101011

output

699063

样例二

input

00001100100101110011110011100010011010101011001010

output

932640914

限制与约定

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

测试点编号 n 1n≤20 2 3n≤100 4 5 6 7n≤5000 8 9 10 11 12 13n≤50000 14 15 16 17 18 19 20

对于全部数据1≤n≤50000,输入数据中的串是一个01串。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

00101110101110101011
699063

样例 2

00001100100101110011110011100010011010101011001010
932640914