← 返回题目列表

AtCoder · agc048_f

F. 01 条记录

中文机器翻译题面 查看原题

分数: 2200 点

问题陈述

Snuke 收到了一块大黑板。 他对这个礼物很满意,先写了一些正整数。 然后,他重复下面的操作,直到黑板上没有写出整数:

  • 选择黑板上写的一个整数并将其擦掉。 让 x 是被删除的整数。 然后,记录剩余的 x 除以 2 在他的笔记本上。 最后,如果 x \geq 2,写入一个新整数 黑板上的 x-1 。

Snuke的记录由字符串表示 S 组成 0 和 1,其中 S_i 是所选整数除以的余数 2 在 i第次操作。

Snuke 忘记了他第一次在黑板上写下的正整数组合。 根据以字符串形式给出的信息 S,找出他第一次在黑板上写下的正整数的可能组合的数量。 在这里,我们考虑组合 a 和 b 存在整数时不同的正整数 v 这样的次数 v 发生于 a 和 v 发生于 b 不同。 由于计数可能很大,因此对其进行模计算 (10^9+7)。 另外,Snuke 的记录也可能不正确,并且没有正整数的组合满足条件。在这种情况下,只需回答 0.

约束

  • 1 \leq |S| \leq 300
  • S 是一个由以下组成的字符串 0 和 1.

输入

输入由标准输入按以下格式给出:

S

输出

打印黑板上写的正整数的可能组合数,取模 (10^9+7).


示例输入 1

101

示例输出 1

2

黑板上写的整数有两种可能的组合: \{1,2\} 和 \{3\}.


示例输入 2

100

示例输出 2

0

黑板上没有可能的整数组合。


示例输入 3

010101

示例输出 3

3

黑板上写的整数有三种可能的组合: \{2,2,2\}, \{2,4\},和 \{6\}.


示例输入 4

11101000111110111101001011110010111110101111110111

示例输出 4

3904