你认为计数很容易吗？当你不完全理解你正在计数的对象时，情况就不是这样了。

我们称一个 $2N$ 位的整数 $X$（可能含有前导零）是有趣的（amusing），如果存在两个 $N$ 位的整数 $a$ 和 $b$（同样可能含有前导零）满足 $a + b = 10^N$，且对于每个数字 $d$（$0 \le d \le 9$），都有 $S_d(X) = S_d(a) + S_d(b)$ 成立，其中 $S_d(P)$ 表示数字 $d$ 在 $P$ 的十进制表示中出现的次数。

例如，数字 $46$（$4 + 6 = 10^1$）、$9820$（$98 + 02 = 10^2$）和 $08362090$（$6020 + 3980 = 10^4$）都是有趣的。

给你一个长度为偶数的由数字和问号组成的序列。求将问号替换为数字以获得一个有趣数字的方法数，模 $10^9 + 7$。

输入格式

输入只有一行，包含一个非空的由数字和问号组成的序列。序列的长度为偶数且不超过 $10^5$。问号的数量不超过 $1000$。

输出格式

输出所求的方法数模 $10^9 + 7$ 的结果。

样例

输入样例 1

2?7?

输出样例 1

4

输入样例 2

29?2?3

输出样例 2

0

输入样例 3

?820

输出样例 3

2