题目描述

给定一个串，由 0，1，2，*，? 组成。求将?替换成其他字符中的任意一个，使原串合法的方案数。将*视为雷，数字就是数字，合法为扫雷地图的合法性。

PS：数字 $i$ 表示以 $i$ 为中心的九宫格中只有 $i$ 个雷。如 2* 是非法的，而 *2* 是合法的。

输入格式

一个字符串（长度在 $1000000$ 以内），仅由 0，1，2，*，? 组成。

输出格式

方案数，对 $1000000007$ 取模。

### 题目描述

给定一个串，由 `0`，`1`，`2`，`*`，`?` 组成。求将`?`替换成其他字符中的任意一个，使原串合法的方案数。将`*`视为雷，数字就是数字，合法为扫雷地图的合法性。

PS：数字 $i$ 表示以 $i$ 为中心的九宫格中只有 $i$ 个雷。如 `2*` 是非法的，而 `*2*` 是合法的。

### 输入格式

一个字符串（长度在 $1000000$ 以内），仅由 `0`，`1`，`2`，`*`，`?` 组成。

### 输出格式

方案数，对 $1000000007$ 取模。