AtCoder 图片原名已被搁置;此后,原始图像取自英语原文,现已完整保存。

可复制的 PDF 提取文本
Gennady Korotkevich Contest 1
Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013
Problem C. Counting Amusing Numbers
Input le: can.in
Output le: can.out
Time limit: 2 seconds
Memory limit: 256 megabytes
Do you think that counting is easy? This is not the case when you don't fully understand objects
that you are counting.
Let's call a 2N-digit integer X (possibly with leading zeroes) amusing if two N-digit integers a
and b (again, possibly with leading zeroes) exist such that a+b = 10N and Sd(X) = Sd(a)+Sd(b)
holds for every digit d, where Sd(P) (0 ≤d ≤9) is the number of occurrences of digit d in the
decimal representation of P. For example, numbers 46 (4 + 6 = 101), 9820 (98 + 02 = 102) and
08362090 (6020 + 3980 = 104) are amusing.
You are given a sequence of digits and question marks of an even length. Find the number of ways
to replace question marks with digits to get an amusing number, modulo 109 + 7.
Input
The only line of the input le contains a non-empty sequence of digits and question marks. The
length of the sequence is even and doesn't exceed 105. The number of question marks doesn't
exceed 1000.
Output
Output the sought number of ways modulo 109 + 7.
Examples
can.in can.out
2?4? 4
29?2?3 0
?820 2
Page 3 of 10