Інтервал
Визначте кількість чисел, які входять у замкнутий інтервал [X, Y], і які можна подати у вигляді суми різних степенів числа b (для подання довільного числа Z[X, Y] кожную степінь b можна застосувати не більше одного разу). Тобто потрібно порахувати кількість Z[X, Y], які можуть бути подані у вигляді:
Z = a_nb^n + a_{n-1}b^{n-1} + ... + a_1b^1 + a_0b^0, i, a_i{0, 1}
Вхідні дані
У першому рядку вхідного файлу містяться три числа X, Y та b (1 ≤ X ≤ Y ≤ 10^100, 2 ≤ b ≤ 10), відокремлені пропусками.
Вихідні дані
У єдиному рядку вихідного файлу виведіть кількість чисел у інтервалі [X, Y], які можна подати у вигляді суми різних степенів числа b.
Примітка:
X=4, Y=10, b=3: 4=3^1+3^0; 9=3^2; 10=3^2+3^0
X=1, Y=12, b=2: 1=2^0; 2=2^1; 3=2^1+2^0; 4=2^2; 5=2^2+2^0; 6=2^2+2^1; 7=2^2+2^1+2^0;
8=2^3; 9=2^3+2^0; 10=2^3+2^1; 11=2^3+2^1+2^0; 12=2^3+2^2.