e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Number systems

Number systems

Chuck Norris counted to infinity. Twice.

(Internet-folklore)

The young mathematician Vovochka is not lazy, so he wrote out all positive integers in ascending order. In a fit of diligence he translated all the numbers of the series into the number system with the base b. Then Vovochka struck out all the numbers of the series, which are a record of some number in the number system with the base c.

Vovochka's diligence was over, and he asked you, as his programmer friend, to find the n-th non-crossed number of the series. Help the young mathematician Vovochka!

Input

Three numbers n, b and c (1n107, 2 < c < b6). In number systems with bases larger than 10 as digits except 0, ..., 9 the lowercase letters of the Latin alphabet a, ..., z are used.

Output

Print (in decimal system) the n-th non-crossed number of the series.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 3 2
Output example #1
5
Input example #2
1 3 2
Output example #2
2
Source 2009 Цикл интернет-олимпиад для школьников. Первая олимпиада, базовый уровень. 19 сентября, Задача А