CF404D Minesweeper 1D

游戏“扫雷 1D”在一条正方形格子的直线上进行，这条线的高度为 1 个格子，宽度为 $n$ 个格子。有些格子里放有地雷。如果一个格子里没有地雷，那么它里面的数字从 0 到 2，表示它相邻格子里的地雷总数。 例如，合法的游戏场地可以是：001\*2\*\*\*101\*。用“\*”标记的格子里有地雷。请注意，在合法的场地中，数字表示相邻格子里的地雷数。例如，场地 2\* 是不合法的，因为数值为 2 的格子必须有两个相邻格子里有地雷。 Valera 想制作一个合法的“扫雷 1D”游戏场地。他已经画好了宽度为 $n$ 的格子，将一些地雷放在了场地上，并在某些格子中填写了数字。现在他想知道，还有多少种方法可以填充剩余的格子（包括放置地雷或填写数字），使得最终得到的是一个合法的场地。

第一行输入一个无空格的字符序列 $s_1s_2...s_n$，$1 \leq n \leq 10^6$，只包含“\*”、“？”和数字“0”、“1”或“2”。如果 $s_i$ 等于“\*”，那么第 $i$ 个格子里有地雷。如果 $s_i$ 等于“？”，那么 Valera 还没有决定这个格子填什么。如果 $s_i$ 是一个数字，则表示该格子已填写了这个数字。

输出一个整数，表示 Valera 有多少种填充剩余格子的方法，使得最终得到一个合法的场地。 由于答案可能很大，请输出对 $1000000007$（$10^9+7$）取模后的结果。

在第一个测试样例中，可以得到如下合法的场地：001\*\*1、001\*\*\*、001\*2\*、001\*10。 由 ChatGPT 5 翻译