题目描述

神犇 xzyo 听说 sl 很弱，于是出了一题来虐一虐 sl。

一个长度为 $2n$（可能有前导 $0$）的非负整数 $x$ 是 good 的，当且仅当存在两个长度为 $n$（可能有前导 $0$）的非负整数 $a,b$ 满足 $a+b=10^n$，并且对于 $0\sim 9$ 每个数位 $d$，都有 $S_d(x)=S_d(a)+S_d(b)$（$S_d(x)$ 为 $x$ 的十进制中 $d$ 出现了多少次）。例如 $0829$ 是 good 的，$98+02==100$。

给出一个长度为 $2n$ 的数，其中有些位置是问号。将每个问号替换为 $0\sim 9$ 任意一个数位后，有多少个 good 数，答案对 $10^9+7$ 取模。

输入格式

一行长度为 $2n$ 的字符串，有 $0\sim 9$ 和 ? 构成。

输出格式

一个整数表示答案。

样例

2?4?

4

另有若干组大样例位于附加文件中。

数据范围

设 $m$ 为 ? 的个数。

• 对于 $30\%$ 的数据，$n\le 6$。
• 对于另外 $30\%$ 的数据，$m\le 6$。
• 对于 $100\%$ 的数据，$1\le n\le 5\times 10^4$，$0\le m\le \min(n,10^3)$。