← 返回题目列表

Codeforces · 404/D

D. 扫雷 1D

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

游戏“扫雷1D”是在一行方格上进行的,该行的高度为1个方格,该行的宽度为n个方格。有些方块里藏着炸弹。如果一个方格不包含炸弹,则它包含 0 到 2 之间的数字——相邻方格中的炸弹总数。

例如,正确的播放字段如下所示:001*2***101*。标有“*”的单元格包含炸弹。请注意,在正确的字段中,数字代表相邻单元格中的炸弹数量。例如,字段 2* 不正确,因为值为 2 的单元格必须有两个带有炸弹的相邻单元格。

Valera 想要制作一个正确的场地来玩“扫雷 1D”。他已经画了一个宽度为 n 个单元格的正方形区域,在该区域上放置了几颗炸弹,并在一些单元格中写入了数字。现在他想知道如果我们最终得到正确的字段,有多少种方法可以用炸弹和数字填充剩余的单元格。

输入

第一行包含不带空格的字符序列 s1s2... sn (1 ≤ n ≤ 106),仅包含字符“*”、“?”以及数字“0”、“1”或“2”。如果字符 si 等于“*”,则该字段的第 i 个单元格包含炸弹。如果字符 si 等于“?”,则 Valera 尚未决定在第 i 个单元格中放入什么内容。字符si,相当于一个数字,代表第i个方格中写入的数字。

输出

打印一个整数 — Valera 可以填充空单元格并获得正确字段的方式数。

由于答案可能相当大,因此打印它模 1000000007 (109 + 7)。

示例

输入 #1

?01???

输出 #1

4

输入 #2

?

输出 #2

2

输入 #3

**12

输出 #3

0

输入#4

1

输出#4

0

注意

在第一个测试样本中,您可以获得以下正确字段:001**1、001***、001*2*、001*10。