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

시간 제한2초메모리 제한1024 MB

요약

자연수를 b진법으로 적은 뒤, 그 표현이 c진법 수의 표기로도 성립하는 수를 지우고 남은 n번째 수를 구한다.

난이도: 보통10점 중 7점
유형: 수학, 정수론, 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

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

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

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

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

입력

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

출력

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

예제3

예제 1
입력
```
2 3 2
```
예상 출력
```
5
```
예제 2
입력
```
1 3 2
```
예상 출력
```
2
```
예제 3
입력
```
1 36 35
```
예상 출력
```
35
```