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 (1 ≤ n ≤ 107, 2 < c < b ≤ 6). 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.