Homework
Little boy Vanya in mug on a number system were asked the following task: to translate the number of X in radix notation s_1 in s_2. Without thinking, he called for help his best friend Pete, who was famous for the fact that the great know how to count to 10 on the fingers. After a few sleepless nights, the joint efforts of the guys coped with the task.
However, in the next lesson, Vanya asked a similar problem, where X, unfortunately, more than 10. Then they decided to go to Summer School Computer to write the generic program that solves the problem for any X, s_1 and s_2. Your purpose - to fulfill the request of Vanya and Petya.
Input
In the input your program has 3 numbers: the initial number X, the base number systems s_1 and s_2 (2 ≤ s_1, s_2 ≤ 10). The number X in decimal system is less than 2·10^9.
Output
The output should be a number equal to the number of X in the notation s_2, or -1 if the input data is invalid.