← 返回题目列表

AtCoder · agc022_e

E. 中值替换

中文机器翻译题面 查看原题

分数: 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, 1 or ?.

输入

输入由标准输入按以下格式给出:

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.