Problem C
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.

Input

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

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

?3 xor 1? = ?

10