分数: 1600 点
问题陈述
Taichi 认为是一个二进制字符串 X 奇数长度 N is 美丽 如果可以应用以下操作 \frac{N-1}{2} 次,使得结果字符串的唯一字符是 1 :
- 选择三个 连续 位 X 并将它们替换为中位数。例如,我们可以将
00110进入010通过对中间三位应用操作。
太一有一根绳子 S 由字符组成 0, 1 和 ?。 Taichi 想知道用多少种方法来替换问号 1 or 0 这样得到的字符串就很漂亮,模数 10^{9} + 7.
约束
- 1 \leq |S| \leq 300000
- |S| 是奇数。
- 所有字符 S 是
0,1or?.
输入
输入由标准输入按以下格式给出:
S
输出
打印替换问号的方法数,使结果字符串漂亮,取模 10^{9} + 7.
示例输入 1
1??00
示例输出 1
2
有 4 替换问号的方法 0 or 1 :
-
11100:这个字符串很漂亮,因为我们可以先对最后一个进行操作 3 位获取110然后就唯一 3 位获取1. -
11000:这个字符串很漂亮,因为我们可以先对最后一个进行操作 3 位获取110然后就唯一 3 位获取1. -
10100:该字符串并不美观,因为没有操作顺序使得最终字符串为1. -
10000:该字符串并不美观,因为没有操作顺序使得最终字符串为1.
因此,有 2 形成漂亮字符串的方法。
示例输入 2
?
示例输出 2
1
在这种情况下, 1 是唯一美丽的字符串。
示例输入 3
?0101???10???00?1???????????????0????????????1????0
示例输出 3
402589311
记得输出你的答案模数 10^{9} + 7.