\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.}