游戏“扫雷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。