Base Conversion

You are given a number in base \(b_1\) and you are required to convert it to base \(b_2\). The number is represented using digits 0-9 and letters A-Z (where A represents 10, B represents 11, and so on). The conversion relies on the formula:

$$ N = \sum_{i=0}^{k-1} d_i \times b_1^i, $$

where \(d_i\) are the digits of the number (with the least significant digit corresponding to \(i=0\)).

Your task is to perform this conversion and output the number in the new base. Note that the converted number should not have any leading zeros (except in the case the number is 0).

inputFormat

The input consists of two lines:

• The first line contains two integers \(b_1\) and \(b_2\) separated by a space, representing the original base and the target base respectively. Both bases are between 2 and 36 inclusive.
• The second line contains the number in base \(b_1\). The number is given as a string that uses digits 0-9 and uppercase letters A-Z.

outputFormat

Output a single line containing the converted number in base \(b_2\>, using uppercase letters for any digit greater than 9. There should be no extra spaces or leading zeros.

sample

2 10
1010

10