The Great Trickster

Hard as it is to believe, Sanggeun went to the Moon over the winter break. Back at school, he told his friends all about meeting the Selenites — the people of the Moon.

Mostly he explained the number system used on the Moon: the Selenites write numbers in a negative base.

Negative bases are hard for people to grasp. So during his trip, Sanggeun memorized every number between $0$ and $n$ (inclusive) whose representation in base $k$ is identical to its representation in base $-k$. Write a program that counts how many numbers he memorized.

The base-$k$ representation of $x$ is a sequence $a_0, a_1, \ldots, a_p$ satisfying $0 \le a_i < |k|$ and $\sum_{i=0}^{p} a_i k^i = x$.

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

Print the number of integers between $0$ and $n$ whose base-$k$ and base-$(-k)$ representations are the same.

For $n = 21$, $k = 3$, the memorized numbers are $0, 1, 2, 9, 10, 11, 18, 19, 20$. For example, $19 = 201_3 = 201_{-3}$, so its two representations match, whereas $7 = 21_3 = 111_{-3}$, so they do not.

For $n = 21$, $k = 2$, the memorized numbers are $0, 1, 4, 5, 16, 17, 20, 21$.