F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4980. -- 第一题

4980: 第一题

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 28  Solved: 17
[Submit][Status][Discuss]

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

[Submit][Status][Discuss]

HOME Back