Problem M
Methodic Multiplication
The Peano axioms (named after Italian mathematican Giuseppe Peano) are an axiomatic formalization of the arithmetic properties of the natural numbers. We have two symbols: the constant $0$, and a unary successor function $S$. The natural numbers, starting at $0$, are then $0$, $S(0)$, $S(S(0))$, $S(S(S(0)))$, and so on. With these two symbols, the operations of addition and multiplication are defined inductively by the following axioms: for any natural numbers $x$ and $y$, we have
\begin{align*} x + 0 & = x & x \cdot 0 & = 0 \\ x + S(y) & = S(x + y) & x \cdot S(y) & = x \cdot y + x \end{align*}The two axioms on the left define addition, and the two on the right define multiplication.
For instance, given $x = S(S(0))$ and $y = S(0)$ we can repeatedly apply these axioms to derive
\begin{align*} x \cdot y & = S(S(0)) \cdot S(0) = S(S(0)) \cdot 0 + S(S(0))\\ & = 0 + S(S(0)) = S(0 + S(0)) = S(S(0 + 0)) = S(S(0)) \end{align*}Write a program which given two natural numbers $x$ and $y$, defined in Peano arithmetic, computes the product $x \cdot y$.
Input
The input consists of two lines. Each line contains a natural number defined in Peano arithmatic, using at most $1\, 000$ characters.
Output
Output the product of the two input numbers.
| Sample Input 1 | Sample Output 1 |
|---|---|
S(S(0)) S(S(S(0))) |
S(S(S(S(S(S(0)))))) |
| Sample Input 2 | Sample Output 2 |
|---|---|
S(S(S(S(S(0))))) 0 |
0 |
