위대한 사기꾼

믿기 힘들겠지만 상근이는 이번 겨울 방학에 달에 갔다 왔다. 방학이 끝나고 학교로 돌아온 상근이는 친구들에게 달나라 사람(Selenites)을 만난 이야기를 들려주었다.

상근이는 주로 달에서 쓰는 수 체계를 설명했다. 달에서는 음의 진법을 사용한다.

음의 진법은 사람이 이해하기 어렵다. 그래서 상근이는 달을 여행하는 동안 $0$과 $n$ 사이(양 끝 포함)의 수 가운데 $k$진법 표현과 $-k$진법 표현이 같은 수를 모두 외웠다. 상근이가 외운 수의 개수를 구하는 프로그램을 작성하시오.

$x$의 $k$진법 표현은 $0 \le a_i < |k|$이고 $\sum_{i=0}^{p} a_i k^i = x$를 만족하는 수열 $a_0, a_1, \ldots, a_p$이다.

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

$0$과 $n$ 사이의 수 중에서 $k$진법 표현과 $-k$진법 표현이 같은 수의 개수를 출력한다.

$n = 21$, $k = 3$일 때 외운 수는 $0, 1, 2, 9, 10, 11, 18, 19, 20$이다. 예를 들어 $19 = 201_3 = 201_{-3}$이므로 두 표현이 같지만, $7 = 21_3 = 111_{-3}$이므로 같지 않다.

$n = 21$, $k = 2$일 때 외운 수는 $0, 1, 4, 5, 16, 17, 20, 21$이다.