问题陈述

Taichi认为一个长度为奇数$N$的二进制字符串$X$是美丽的，如果可以应用以下操作$\\frac{N-1}{2}$次，使得结果字符串的唯一字符是1：

• 选择$X$的三个连续位，并将它们替换为它们的中值。例如，我们可以通过将操作应用于中间三个位将00110变为010。

Taichi有一个由字符0，1和?组成的字符串$S$。Taichi想要知道替换问号为1或0的方法数量，使得结果字符串是美丽的，模$10^{9} + 7$。

约束条件

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

输入

输入以以下格式从标准输入给出：

$S$

输出

打印替换问号的方法数量，使得结果字符串是美丽的，模$10^{9} + 7$。

样例输入 1

1??00

样例输出 1

2

有四种方法可以用0或1替换问号：

• 11100：这个字符串是美丽的，因为我们可以先对最后三位进行操作得到110，然后对唯一的三位进行操作得到1。

• 11000：这个字符串是美丽的，因为我们可以先对最后三位进行操作得到110，然后对唯一的三位进行操作得到1。

• 10100：这个字符串不是美丽的，因为没有一系列操作使得最终字符串为1。

• 10000：这个字符串不是美丽的，因为没有一系列操作使得最终字符串为1。

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

样例输入 2

?

样例输出 2

1

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

样例输入 3

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

样例输出 3

402589311

记得将答案模$10^{9} + 7$输出。