数位DP特点：求某个区间内，满足某个性质的数的个数。
技巧1：$[X,Y]=>f(Y)-f(X-1)$
技巧2：树

//题意：在[X,Y]之间，B进制表示是由K个1组成的数的个数
#include <iostream>
#include <vector>

using namespace std;

const int N = 35;

int x , y , K , B;
int f[N][N];

void init()
{
    for(int i = 0 ; i < N ; i++)
        for(int j = 0 ; j <= i ; j++)
            if(!j) f[i][j] = 1;
            else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}

int dp(int n)//[0 , n]之间，B进制表示是由K个1组成的数的个数
{
    if(!n) return 0;

    vector<int> nums;
    while(n) nums.push_back(n % B) , n /= B;

    int res = 0;
    int last = 0;//右分支上1的个数
    for(int i = nums.size() - 1 ; i >= 0 ; i--)
    {
        int x = nums[i];
        if(x) //枚举左分支
        {
            res += f[i][K - last]; //当x>0时，自然能枚举第i为不是1的情况(即第i位是0)
            if(x > 1)//当x>1时，还可以枚举第i位是1，这里因为枚举的是左分支，因此不会对last产生影响
            {
                if(K - last) res += f[i][K - last - 1];  //枚举的数是1
                break;   //枚举的数大于1时，因为题目要求B进制表示仅包含0和1，所以当枚举的数大于1时直接退出
            }
            else //x=1，只能继续向下搜索
            {
                last++;  
                if(last > K) break;
            }
        }

        if(!i && last == K) res++;//枚举最后一个右分支，如果恰好已经用完K个1，则方案数加1
    }

    return res;
}

int main()
{
    init();

    cin >> x >> y >> K >> B;

    cout << dp(y) - dp(x - 1) << endl;
}