#include <bits/stdc++.h>
using namespace std;

const int N = 32; // 输入的数据范围2^31-1,也就是整数上界。2进制是最小的进制，32也够了

int l, r;     // 数位DP的区间范围
int k, b;     // k:个进制位为1,b进制
int a[N], al; // 用来分解b进制的数组
int f[N][N];  // f[i][j] i:枚举到的位置 j:已经计算完1的个数,这里需要一点DP的状态描述的思想，只有一维记录到哪了，是无法描述整个当时场景的

/**
 *
 * @param u 当前枚举到的数位
 * @param st  数字1出现的次数
 * @param op  是否贴上界
 * @return  在当前情况下，它 后续 符合条件的一共有多少个数
 */
int dfs(int u, int st, bool op) {
    // 到最后一位数位，是否恰好有k个不同的1,是：贡献价值+1，否：贡献价值+0
    if (u == 0) return st == k;

    if (op == 0 && ~f[u][st]) return f[u][st]; // 不贴上界，并且计算过，返回结果

    /*
    ① 不贴着上界，可以将此区间算满，缓存起来，不用重复计算
    ② 贴上界，每次重新计算

    本题要求：
    (1)如果op = 1, 贴上界
        如果a[u]=0,那么up最大是0,否则,up最大是1,简写成min(a[u],1)
    (2)如果op = 0, 不贴上界,可以选择的范围[0,1],up最大是1
    */
    int ans = 0;
    int up = op ? min(a[u], 1) : 1; // up就是你的极限！本题，这句是一个精华点

    for (int i = 0; i <= up; i++) { // 枚举上限之内的数字(其实，也只有0和1有机会，这还要看up的取值。up=0,跑一次循环；up=1,跑两次循环)
        // 如果i==0,则st+i=st,st不会变大，也不会超过k,此句无影响后面的代码执行。
        // 如果i==1,则表示多选择了一个是1的数位，st+1,有可能已经超过了k的限制，再向后跑深搜就没有了意义，及时止损，剪枝
        if (st + i > k) continue; // 剪枝更健康

        // u-1:继续向低一位进行前进
        // st+i:1的个数变化情况，如果i==0,则表示u这个数位没有选择数字1；如果i==1，则表示u这个数位选择了数字1，不断的向后传递这个信息，用于判断是不是符合条件的数字
        // op && i == a[u] :此参数的含义是是否贴合上限
        // op:原来是贴上界的 &&   i == a[u]: 当前位取值也是贴上界
        // 那么，下面一位是继承前面的结果关系，也就是，它也在贴上界的情况下进行讨论

        // ==的运算优先级　高于　&& ，所以先判断　i == a[u]是第一步，与 op 相 && 是第二步
        ans += dfs(u - 1, st + i, op && i == a[u]);
    }
    // 只记录不受上限限制的个数，受上限限制的每次重新计算
    // 为什么只记录不贴上界的结果，贴上界的为什么不能直接使用结果？
    // 这是因为：如果第一位贴了上界，那么第二位也可能继续贴上界，导致后续的无法取完整，无法直接使用结果
    if (!op) f[u][st] = ans;
    /*这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑lead，这里就是lead就完全不用考虑了*/
    return ans;
}

// 采用类似于前缀和的思想，所以，需要封装成一个calc函数,计算两次，然后取差值
int calc(int x) {
    al = 0;                            // 临时数组a初始化，这里挺有意思，把al=0就相当于全新初始化掉了a,不用采用memset(a,0,sizeof a);
    while (x) a[++al] = x % b, x /= b; // 把x按照进制分解到数组中,下标从1开始
    return dfs(al, 0, true);           // 从最高位开始，目前数字1出现了0次，贴上界
}

int main() {
    memset(f, -1, sizeof f); // 初始化
    cin >> l >> r >> k >> b; // 边界，k个数位是1，b进制
    // 前缀和
    cout << calc(r) - calc(l - 1) << endl;
    return 0;
}