Məsələlər
Интервал
Интервал
\includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg}
\includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg}
Определите количество чисел, входящих в замкнутый интервал \textbf{\[X, Y\]}, представимых в виде суммы различных степеней числа \textbf{b} (для представления любого числа \textbf{Z\[X, Y\]} каждую степень \textbf{b} можно применить не более одного раза). То есть нужно подсчитать количество \textbf{Z\[X, Y\]}, которые могут быть представлены в виде:
\includegraphics{https://static.e-olymp.com/content/a9/a95e3a2fa6a4bb21891b266af71619da5c09face.jpg}
\includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg}
\textbf{Z = a_nb^n + a_\{n-1\}b^\{n-1\} + ... + a_1b^1 + a_0b^0, i, a_i\{0, 1\}}
\InputFile
В первой строке входного файла содержатся три числа \textbf{X}, \textbf{Y} и \textbf{b} (\textbf{1} ≤ \textbf{X} ≤ \textbf{Y} ≤ \textbf{10^100}, \textbf{2} ≤ \textbf{b} ≤ \textbf{10}), разделённые пробелами.
\OutputFile
В единственной строке выходного файла выведите количество чисел в интервале \textbf{\[X, Y\]}, представимых в виде суммы различных степеней числа \textbf{b}.
\Note
\textbf{X=4, Y=10, b=3: 4=3^1+3^0; 9=3^2; 10=3^2+3^0}
\textbf{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;}
\textbf{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.}
Giriş verilənləri #1
15 19 4
Çıxış verilənləri #1
2