#4980. 第一题

内存限制:256 MiB 时间限制:10 Sec

题目描述

神犇xzyo听说sl很弱,于是出了一题来虐一虐sl。一个长度为2n(可能有前缀0)的非负整数x是good的,当且仅当
存在两个长度为n(可能有前缀0)的非负整数a、b满足a+b==10n,并且对于0~9每个数位d,都有Sd(x)==Sd(a)+Sd(
b)(Sd(x)为x的十进制中d出现了多少次)。例如0829是good的,98+02==100。给出一个长度为2n的序列,其中有些
位置是问号。将每个问号替换为0~9任意一个数位后,有多少个good数,答案对1000000007取膜。为了sl不被虐死
,快告诉他怎么写吧。

输入格式

一行长度为2n的字符串,有0~9和?构成。
n≤50000,m≤1000,设m为?的个数

输出格式

一个整数表示答案。

样例

样例输入


			
2?4?

样例输出


			
4

数据范围与提示