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