AT_agc022_e [AGC022E] Median Replace

太一认为，由 $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 \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 翻译