Interval
Bağlı intervalda [X, Y] daxilində olan və b ədədinin müxtəlif qüvvətlərinin cəmi kimi ifadə edilə bilən ədədlərin sayını tapın. Burada hər hansı bir Z[X, Y] ədədini ifadə etmək üçün b ədədinin hər bir qüvvəti yalnız bir dəfə istifadə edilə bilər. Yəni, Z[X, Y] şəklində ifadə edilə bilən ədədlərin sayını hesablamalısınız:
Z = a_nb^n + a_{n-1}b^{n-1} + ... + a_1b^1 + a_0b^0, burada a_i{0, 1}
Giriş verilənləri
Giriş faylının ilk sətirində üç ədəd X, Y və b (1 ≤ X ≤ Y ≤ 10^100, 2 ≤ b ≤ 10) boşluqlarla ayrılmış şəkildə verilir.
Çıxış verilənləri
Çıxış faylının tək sətirində [X, Y] intervalında b ədədinin müxtəlif qüvvətlərinin cəmi kimi ifadə edilə bilən ədədlərin sayını göstərin.
Qeyd:
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.