UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4980. 第一题

统计 下载数据

Description

神犇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不被虐死
,快告诉他怎么写吧。

Input

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

Output

一个整数表示答案。

Sample Input

2?4?

Sample Output

4

Hint

Source