제곱수의 합

문제

모든 자연수는 서로 다른 $2$의 거듭제곱의 합으로 나타낼 수 있다. 예를 들어 $15 = 2^3 + 2^2 + 2^1 + 2^0$이고, $5 = 2^2 + 2^0$이다.

그렇다면 $2$ 대신 다른 정수 $K$의 거듭제곱을 사용하면 어떨까?

$L$ 이상 $R$ 이하의 자연수 중에서 서로 다른 $K$의 거듭제곱의 합으로 나타낼 수 없는 수의 개수를 구해 보자. 사용할 수 있는 거듭제곱은 $K^0, K^1, K^2, \ldots$이며, 각 거듭제곱은 최대 한 번만 사용할 수 있다.

입력

첫째 줄에 세 정수 $L$, $R$, $K$가 공백으로 구분되어 주어진다. $(1 \le L \le R \le 10^{18}; 2 \le K \le 100)$

출력

$L$ 이상 $R$ 이하인 정수 중 $K$의 서로 다른 음이 아닌 정수 거듭제곱의 합으로 표현할 수 없는 정수의 개수를 출력한다.

예제 1

10 20 4

출력 1

8

예제 2

1 1000000000000000000 2

출력 2

0

예제 3

1 1000000000000000000 3

출력 3

999999725122093057

힌트

예제 1에서 $10$ 이상 $20$ 이하의 수 중 서로 다른 $4$의 거듭제곱의 합으로 나타낼 수 있는 수는 다음 세 개이다.

• $16 = 4^2$
• $17 = 4^2 + 4^0$
• $20 = 4^2 + 4^1$

$10$ 이상 $20$ 이하에는 모두 $11$개의 수가 있으므로, 이 세 수를 제외한 $11-3=8$개의 수는 서로 다른 $4$의 거듭제곱의 합으로 나타낼 수 없다.