分数: 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