\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}. \textit{\textbf{Примітка}}: \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.}