eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Системы счисления

Системы счисления

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Чак Норрис досчитал до бесконечности. Дважды.

(Интернет-фольклор)

Юный математик Вовочка столь неленив, что выписал в ряд все натуральные числа в порядке возрастания. В порыве трудолюбия он перевел все числа ряда в систему счисления с основанием b. Потом Вовочка вычеркнул все числа ряда, которые являются записью какого-либо числа в системе счисления с основанием c.

Трудолюбие Вовочки закончилось, и он попросил Вас, как своего друга-программиста, найти n-ое невычеркнутое число ряда. Помогите юному математику Вовочке!

Входные данные

Три числа n, b и c (1n10^7, 2 < c < b6). В системах счисления с основаниями, большими 10 в качестве цифр кроме 0, ..., 9 используются также строчные буквы латинского алфавита a, ..., z.

Выходные данные

Выведите (в десятичной системе счисления) n-ое невычеркнутое число ряда.

Пример

Входные данные #1
2 3 2
Выходные данные #1
5
Входные данные #2
1 3 2
Выходные данные #2
2
Источник 2009 Цикл интернет-олимпиад для школьников. Первая олимпиада, базовый уровень. 19 сентября, Задача А