分值：$1600$ 分

问题描述

Taichi 认为一个奇数长度 $N$ 的二进制字符串 $X$ 是美丽的，如果可以执行以下操作 $\frac{N-1}{2}$ 次，使得最终字符串只包含一个字符 1：

• 选择 $X$ 的三个连续比特，并将它们替换为它们的中位数。例如，我们可以将 00110 转换为 010，通过对中间三个比特执行操作。

Taichi 有一个字符串 $S$，由字符 0、1 和 ? 组成。Taichi 想知道有多少种方法可以将问号替换为 1 或 0，使得结果字符串是美丽的，答案取模 $10^9 + 7$。

约束条件

• $1 \leq |S| \leq 300000$
• $|S|$ 是奇数。
• $S$ 的所有字符要么是 0，要么是 1，要么是 ?。

输入

输入通过标准输入提供，格式如下：

$S$

输出

打印将问号替换为 0 或 1 使得结果字符串是美丽的方式的数量，结果对 $10^9 + 7$ 取模。

1??00

2

有 $4$ 种方法可以替换问号为 0 或 1：

• 11100：这个字符串是美丽的，因为我们可以首先对最后 $3$ 位执行操作得到 110，然后对唯一 $3$ 位执行操作得到 1。
• 11000：这个字符串是美丽的，因为我们可以首先对最后 $3$ 位执行操作得到 110，然后对唯一 $3$ 位执行操作得到 1。
• 10100：这个字符串不是美丽的，因为没有序列的操作可以使最终字符串为 1。
• 10000：这个字符串不是美丽的，因为没有序列的操作可以使最终字符串为 1。

因此，有 $2$ 种方法可以形成一个美丽的字符串。

?

1

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

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

402589311

记得输出答案对 $10^9 + 7$ 取模。