Any Base To Any Base

easy

1. You are given a number n.
2. You are given a base b1. n is a number on base b.
3. You are given another base b2.
4. You are required to convert the number n of base b1 to a number in base b2.

Input Format

A number n A base b1 A base b2

Output Format

A number of base b2 equal in value to n of base b1.

Constraints

0 &lt;= n &lt;= 512
2 &lt;= b1 &lt;= 10
2 &lt;= b2 &lt;= 10

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

111001
2
3

Output

Any Base To Decimal

Any Base Addition