题目描述

太一认为，由 $0$ 和 $1$ 组成的奇数长度 $N$ 的字符串 $X$，如果满足以下条件，则是美丽的。条件如下：可以进行 $\frac{N-1}{2}$ 次如下操作，使得最终字符串唯一的字符为 $1$。

• 选择 $X$ 中连续的 $3$ 个比特，并用它们的中位数替换这三个比特。例如，对 00110 的中间 $3$ 个比特应用该操作后，字符串变为 010。

太一有一个由 0、1、? 组成的字符串。他想知道，将每个 ? 替换为 0 或 1，能够得到美丽字符串的方法数。请输出该方法数对 $10^{9}+7$ 取模的结果。

输入格式

输入从标准输入读取，格式如下：

$S$

输出格式

输出将每个 ? 替换为 $0$ 或 $1$，能够得到美丽字符串的方法数，对 $10^{9}+7$ 取模。

样例 1

输入

1??00

输出

2

样例 2

输入

?

输出

1

样例 3

输入

?0101???10???00?1???????????????0????????????1????0

输出

402589311

说明/提示

限制条件

• $1 \leq |S| \leq 300000$
• $|S|$ 是奇数。
• $S$ 的所有字符均为 0、1 或 ?。

样例解释 1

将 ? 替换为 0 或 1 的方法共有 $4$ 种：

• 11100：该字符串是美丽的。因为首先对最后 $3$ 个比特应用操作，得到 110，再对整个字符串应用操作，得到 1。
• 11000：该字符串是美丽的。因为首先对最后 $3$ 个比特应用操作，得到 110，再对整个字符串应用操作，得到 1。
• 10100：该字符串不是美丽的。因为不存在操作顺序能使最终字符串为 1。
• 10000：该字符串不是美丽的。因为不存在操作顺序能使最终字符串为 1。

因此，可以得到美丽字符串的方法有 $2$ 种。

样例解释 2

在这种情况下，只有 1 是唯一的美丽字符串。

样例解释 3

不要忘记输出答案对 $10^{9}+7$ 取模。

由 ChatGPT 4.1 翻译