题目描述

すぬけくん得到了一个大黑板。すぬけくん非常高兴，首先在黑板上写下了一些正整数。接着，すぬけくん不断重复以下操作，直到黑板上的整数全部消失为止。

• 从黑板上选择一个整数并擦除。设被擦除的整数为 $x$。然后，将 $x$ 除以 $2$ 的余数记录在笔记本上。最后，如果 $x \geq 2$，则将 $x-1$ 写回黑板。

すぬけくん的记录由一个仅包含 0 和 1 的字符串 $S$ 表示。也就是说，すぬけくん在第 $i$ 次操作中选择的整数除以 $2$ 的余数为 $S_i$。

すぬけくん忘记了最初在黑板上写下的正整数的组合。请根据字符串 $S$，求出作为最初黑板上正整数组合的可能方案数。这里，正整数组合 $a$ 和 $b$ 不同，意味着存在某个整数 $v$，使得 $a$ 中 $v$ 的个数与 $b$ 中 $v$ 的个数不同。由于答案可能非常大，请输出对 $10^9+7$ 取模的结果。如果すぬけくん的记录有误，无法满足条件，则输出 $0$。

输入格式

输入通过标准输入给出，格式如下：

$S$

输出格式

输出作为最初黑板上正整数组合的可能方案数，对 $10^9+7$ 取模。

样例 1

输入

101

输出

2

样例 2

输入

100

输出

0

样例 3

输入

010101

输出

3

样例 4

输入

11101000111110111101001011110010111110101111110111

输出

3904

说明/提示

限制

• $1 \leq |S| \leq 300$
• $S$ 是仅由 0 和 1 组成的字符串。

样例解释 1

作为最初黑板上整数的组合可能有 $\{1,2\}$、$\{3\}$ 共 $2$ 种。

样例解释 2

不存在满足条件的最初黑板上整数组合。

样例解释 3

作为最初黑板上整数的组合可能有 $\{2,2,2\}$、$\{2,4\}$、$\{6\}$ 共 $3$ 种。

由 ChatGPT 4.1 翻译