On Mars, the base k number system is used. Unlike the decimal number system we are used to, in this number system there are k digits with values from 0 to k - 1 , and the weight of the digit in the i -th digit is equal to k
i .
For example, let k = 8 . The entry 357
8 means the number 3·8 2 + 5·8 + 7 , in the decimal number system more familiar to earthlings, this number is written as 239
10 . And the number 192
10 , in the number system with base 8 is written as 300
8 .
Ildar — young Martian, and he is very fond of round numbers. Ildar calls a number sufficiently round if its notation in the number system with base k ends with at least n zeros. Today Ildar wants to find i -th in order sufficiently round number.
Help Ildar, find the i -th natural number that is sufficiently round in the number system with base k and output it in the decimal number system. Ildar is very friendly and guarantees that the answer in decimal not exceed 10
18 .
Input
All restrictions on numbers in this problem are given in the decimal number system. All numbers in the input are also written in decimal notation.
The first line of the input contains the number k — the base of the number system used by Ildar ( 2 ≤ k ≤ 10
9 ).
The second line of the input contains the number n — the minimum number of zeros at the end of a sufficiently round number ( 0 ≤ n ≤ 100 ).
The third line of the input contains the number i — ordinal of a sufficiently round number that Ildar is interested in ( 1 ≤ i ≤ 10
9 ).
Imprint
Print one number — notation in decimal notation of the i-th in order sufficiently round in the number system with base k of a natural number. It is guaranteed that the answer does not exceed 10
18 .
Note that the response may not fit in the standard 32-bit data type. It is necessary to use a 64-bit type, in pascal it is called « int64 ", in C++ " long long ", in Java " long ". If you're writing in Python, don't worry, Python's built-in integer type has no limits on the size of a number.
| # |
Input |
Output |
| 1 |
8
2
2 |
192 |