该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

本题强烈建议仔细阅读下方样例解释部分，很有助于帮助你理解题意。

当然，$TooY0ung$ 的建议是每道题目都仔细看样例。

$TooY0ung$ 某天坐在办公室内沉思，决定开发一个关于字符串的游戏，游戏规则如下：

给出一个字符串，字符串内只包含五种字符：0，1，2，?，*，含义如下：

0 代表在这个位置 相邻 的左边和右边有 $0$ 个 * 符号，

1 代表在这个位置 相邻 的左边和右边有 $1$ 个 * 符号，

2 代表在这个位置 相邻 的左边和右边有 $2$ 个 * 符号，

? 代表在这个位置可以填入任意一个 0 或者 1 或者 2 或者 * 符号，* 代表在这个位置上为 * 符号。

现在 $TooY0ung$ 想知道，在合法的情况下，? 位置的符号填入有多少种方案，如果没有任何方案合法，则答案为 $0$。

由于方案数可能很多，答案要求对 $10^9+7$ 取模。

关于合法的解释：

在 ? 处填入符号后，不会产生矛盾。

输入格式

输入包含一行，一个字符串。

输出格式

输出为一行，字符串合法填入的方案。

填入规则以及合法条件，见题目描述。

?

2

1

0

样例 1 解释

字符串长度为 $1$ ，仅有一个位置，? 位置可以填入：

$1.$ 0，表示左右都没有 *。

$2.$ *，表示这个位置为 *。

其余的方案均不合法，

若填入 1，代表左右有 $1$ 个 *，字符串长度为 $1$，无左右，显然不可能。

若填入 2，代表左右有 $2$ 个 *，字符串长度为$1$，无左右，显然不可能。

样例 2 解释

字符串长度为 $1$，仅有一个位置，且为符号 1，

1 代表左右有 $1$ 个 *，字符串长度为 $1$，无左右，显然不可能。

数据规模与约定

对于 $50\%$ 的数据，$1 \le |S| \le 100$。$|S|$ 表示字符串长度。

对于 $100\%$ 的数据，$1 \le |S| \le 10^6$。