## EQ2 - A Famous Equation

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=22Output: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 |