## EQ2 - A Famous Equation

no tags

Mr. B wrote an addition equation such as 123+321=444 on the blackboard after class. Mr. G removes some of the digits and makes it look like “1?3+??1=44?”. After Mr. B realizes some digits are missing, he wants to recover them. Unfortunately, there may be more than one way to recover the equation. For example “1?3+??1=44?” can be recovered to “123+321=444” or “143+301=444” and many other possible solutions. Your job is to determine the number of different possible solutions.

### Input

Each test case describes a single line with an equation like a+b=c which contains exactly one plus sign + and one equal sign = with some digits are missing and replaced with ?. You may assume a, b and c are non-negative integers, and the length of each number is no more than 9. In the other words, the equation will contain three integers less than 1,000,000,000.

### Output

For each test case, display a single line with its case number and the number of possible solutions to recover the equation.

### Example

```Input:
7+1?=1?
?1+?1=22

Output:
Case 1: 3
Case 2: 1
```

Explanation

There are three solutions for the first case:

7+10=17, 7+11=18, 7+12=19

There is only one solution for the second case:

11+11=22

Note that 01+21=22 is not a valid solution because extra leading zeros are not allowed.

hide comments hamjosh1: 2016-12-23 10:10:59 be sure of using long long cost me wa's btw enjoyed a lot :D

 Added by: Fudan University Problem Setters Date: 2012-05-25 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: g201513's own problem, used in FDU Local Contest 2012