На Марсе используют систему счисления с основанием k . В отличие от привычной нам десятичной системы счисления, в этой системе счисления k цифр со значениями от 0 до k - 1 , а вес цифры в i -м разряде равен k
i .
Например, пусть k = 8 . Запись 357
8 означает число 3·8 2 + 5·8 + 7 , в более привычной землянам десятичной системе счисления это число записывается как 239
10 . А число 192
10 , в системе счисления с основанием 8 записывается как 300
8 .
Ильдар — юный марсианин, и он очень любит круглые числа. Ильдар называет число достаточно круглым , если его запись в системе счисления с основанием k заканчивается хотя бы на n нулей. Сегодня Ильдар хочет найти i -е по порядку достаточно круглое число.
Помогите Ильдару, найдите i -е достаточно круглое в системе счисления с основанием k натуральное число и выведите его в десятичной системе счисления. Ильдар очень дружелюбен и гарантирует, что ответ в десятичной системе счисления не превосходит 10
18 .
Входные данные
Все ограничения на числа в этой задаче заданы в десятичной системе счисления. Все числа во вводе также записаны в десятичной системе счисления.
Первая строка входных данных содержит число k — основание системы счисления, которую использует Ильдар ( 2 ≤ k ≤ 10
9 ).
Вторая строка входных данных содержит число n — минимальное количество нулей на конце достаточно круглого числа ( 0 ≤ n ≤ 100 ).
Третья строка входных данных содержит число i — порядковый номер достаточно круглого числа, которое интересует Ильдара ( 1 ≤ i ≤ 10
9 ).
Выходные данные
Выведите одно число — запись в десятичной счистеме счисления i -го по порядку достаточно круглого в системе счисления с основанием k натурального числа. Гарантируется, что ответ не превышает 10
18 .
Обратите внимание, что ответ может не поместиться в стандартный 32-битный тип данных. Надо использовать 64-битный тип, в паскале он называется « int64 », в C++ « long long », в Java « long ». Если вы пишете на языке Python, то волноваться не надо, в Python встроенный целочисленный тип не имеет ограничений на величину числа.
| № |
Входные данные |
Выходные данные |
| 1 |
8
2
2 |
192 |