← 返回题目列表

AtCoder · icpc2015summer_day3_c

C. 数有趣的数字

中文机器翻译题面 查看原题

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

Counting Amusing Numbers - 原题 PDF
赛事原始英文题册页面
可复制的 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