题目描述

给定一个字符串$\red{str,}$由$\red{0,1,2,*,?}$组成。

将$\red{*}$视为雷,数字就是数字,合法为扫雷地图的合法性。

现在你可以将$\red{?}$替换成其他字符中的任意一个，问能够使原串合法的方案数。

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

输入格式

一个字符串,仅由$\red{0,1,2,*,?}$组成.

输出格式

仅一个数，对$\red{10^9+7}$取模。

样例

输入样例

?01???

输出样例

4

提示

样例解释：

在样例中，我们可以得到一下四种合法的方案：

$\red{001~}$ $\red{*~}$ $\red{*1}$

$\red{001~}$ $\red{*~}$ $\red{**}$

$\red{001~}$ $\red{*~}$ $\red{2*}$

$\red{001~}$ $\red{*~}$ $\red{10}$

数据范围：

对于$\red{30\%}$的数据，满足$\red{|str| ≤}$ $\red{10，}$

对于所有的数据，满足$\red{|str| ≤}$ $\red{10^6}$