흥미로운 수

로만은 자신이 흥미롭다고 느끼는 수를 수집한다. 예를 들어 그는 지금 $k$진법으로 썼을 때 0이 홀수 개로 끝나는 양의 정수를 흥미롭다고 여긴다. 예를 들어 $k=2$일 때 이런 수는 $2_{10}=10_2$, $24_{10}=11000_2$이다.

로만은 컬렉션을 채우기 위해 이런 수를 오름차순으로 나열했을 때 $n$번째 수를 찾으려 한다. $n$을 꽤 크게 잡아서 손으로는 찾을 수 없다.

로만을 도와 컬렉션을 채우는 데 필요한 수를 찾는 프로그램을 작성하시오.

첫째 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \le n \le 10^{15}$, $2 \le k \le 10$).

$k$진법으로 썼을 때 0이 홀수 개로 끝나는 수를 오름차순으로 나열했을 때 $n$번째 수를 출력한다. 이 수는 십진법으로 출력해야 한다.