Interesting Numbers

Time limit2sMemory limit1024 MB

Summary

Find the n-th smallest positive integer whose base-k representation ends with an odd number of trailing zeros.

Level: Medium7 of 10
Topics: Math, Combinatorics, Binary search, Number theory
Solved: No attempts yet

Statement

Roman collects numbers that seem interesting to him. For example, he currently considers a positive integer interesting if its representation in base $k$ ends with an odd number of zeros. For instance, when $k=2$ such numbers are $2_{10}=10_2$ and $24_{10}=11000_2$ .

To add to his collection, Roman wants to find the $n$ -th smallest such number. Since he chose $n$ large enough, he cannot find it by hand.

Help Roman by writing a program that finds the number he needs to complete his collection.

Input

The first line of the input contains two integers $n$ and $k$ ( $1 \le n \le 10^{15}$ , $2 \le k \le 10$ ).

Output

Output the $n$ -th smallest number whose representation in base $k$ ends with an odd number of zeros. Output this number in decimal.

Examples2

Example 1
Input
```
1 2
```
Expected output
```
2
```
Example 2
Input
```
10 10
```
Expected output
```
110
```