问题描述

Snuke收到了一个大黑板。他很高兴地接受了这个礼物，首先在黑板上写下一些正整数。然后，他重复以下操作，直到黑板上没有整数为止：

• 选择一个写在黑板上的整数并擦除它。令 $x$ 为被擦除的整数。然后，将 $x$ 对 $2$ 取余数记录在笔记本上。最后，如果 $x \geq 2$，在黑板上写入一个新的整数 $x-1$。

Snuke的记录由一个字符串 $S$ 表示，其中 $S_i$ 是第 $i$ 次操作中所选整数对 $2$ 取余数的结果。

Snuke忘记了他最初在黑板上写的正整数的组合。根据字符串 $S$ 提供的信息，找出可能的初始正整数组合的数量。在这里，当存在整数 $v$，使得在组合 $a$ 中 $v$ 出现的次数与在组合 $b$ 中 $v$ 出现的次数不同时，我们认为组合 $a$ 和组合 $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