XOR Equation

Image by
geralt

Once there was a great general Paul who issued the following warning:

Suppose aliens invade the earth and threaten to obliterate it in a year’s time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world’s best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.

However this time, when the aliens come, they only write
down a single line of XOR equation in the form of $a$ `xor` $b~ =~
c$ (here “`xor`” denotes the bitwise
XOR operator) with some digits hidden in question marks. The
aliens ask humans to calculate the number of ways that this
equation can be satisfied. For example, two ways to satisfy
$?3$ `xor` $1?~ =~
?$ are $13$ `xor` $10~ =~
7$ and $13$ `xor` $13~ =~
0$. Obviously, the aliens will not be happy if humans
count it wrong.

The input has a single line that contains the XOR equation
$a$ `xor` $b~ =~
c$ with some digits replaced by question marks. A single
space is used to separate the integers, the string “`xor`”, and the equals sign. The three integers
$a$, $b$, and $c$ are non-negative and written in
base-$10$ without leading
zeroes. No integer has more than $9$ digits. There is at least one and
at most ten question marks in the equation.

Output the number of ways in which the XOR equation can be satisfied after all the question marks are replaced by digits.

Sample Input 1 | Sample Output 1 |
---|---|

?3 xor 1? = ? |
10 |