Problem
Little Arseniy was given the following task at the number system circle: convert the number X in the number system s1 to the number system s2. Without thinking twice, he called his best friend Dobrynya for help, who was famous for being remarkably able to count to 10 on his fingers. After several sleepless nights, the guys coped with the task with common efforts.
However, at the next lesson, Arseniy was given a similar problem, where X, unfortunately, exceeded 10. Then the guys decided to apply to the Summer Computer School with a request to write a universal program that solves the problem for any X, s1 and s2. Your goal – fulfill the request of Arseniy and Dobrynya.
Input
Your program is given 3 numbers as input: the original number X, bases s1 and s2 (\(2 <= s1,\ s2 <= 10\)). The number X in decimal notation does not exceed \(2 \cdot 10^9\).
Output
The output should contain a single number equal to the number
X in the number system
s2, or
-1 if the input is invalid.< br />
Examples
| # |
Input |
Output |
| 1 |
101 2 10 |
5 |
| 2 |
200 2 10 |
-1 |