A Famous Equation#3585
Sign in

A Famous Equation

1 second
32 megabytes
Hard

Mr. B writes 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?". Here "?" denotes removed digits. After Mr. B realizes some digits are missing, he wants to recover them. Unfortunately, there may be more than one way to complete the equation. For example, "1?3+??1=44?" can be completed to "123+321=444", "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 question marks "?" representing missing digits. You may assume , , and are non-negative integers, and the length of each number is no more than . In other words, the equation will contain three integers less than .

Output

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

Examples

Example 1

Loading
Loading

Note

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.