Woburn Challenge 1996

In normal everyday usage, numbers are thought of in base ten. The reason for this is naturally due to humans having ten fingers on which to perform mathematical operations such as add, subtract and multiply. However, in computer technology, the use of low and high voltage states lends itself to thinking of operations defined on having only these two states. Hence, the binary system as a descriptive tool in computers is quite useful. Moreover, we could easily have a use for other number systems (cartoon characters counting in base 8, some alien species counting in base 97).

Your task is to take two different-base numbers, calculate their product, and return the answer in another base.

For example, "Find ~12_8 \times 35_9~ in base 10."

Input Specification

The input file contains 5 data sets.
The first line of each data set is the first number and its base.
The second line of each data set is the second number and its base.
The third line of each data set is the base in which the product is to be reported.
All bases will be integers from 2 to 10 inclusive.

Output Specification

Give the product of the numbers in the specified base.
Each product will be less than or equal to 2 billion (base ten).

Sample Input

12 8
35 9
10
121 7
121 7
7

(and 3 more inputs)

Sample Output

320
14641