#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int l, r;     // 数位DP的区间范围
int k, b;     // k:个进制位为1,b进制
int a[N], al; // 用来分解b进制的数组

// 将x转化为b进制
void calc(int x, int b) {
    al = 0;
    memset(a, 0, sizeof a);
    while (x) a[++al] = x % b, x /= b;
}

/*
通过了 7/14个数据
一半的分数也是OIer的梦想！
*/
int res;
int main() {
    cin >> l >> r >> k >> b;
    // 1、将[l,r]之间所有数字进行b进制分解
    for (int i = l; i <= r; i++) {
        calc(i, b);

        int cnt = 0;
        bool bad = false; // 是不是全是0或1，一旦是bad=true,表示出现了大于数字1的数位，此时，一票否决~！

        // 2、检查是不是存在大于1的，大于1的是无效数字，跳过
        for (int j = 1; j <= al; j++) {
            if (a[j] > 1) {
                bad = true;
                break;
            }
            // 3、统计一下1出现的次数
            if (a[j] == 1) cnt++;
        }
        // 4、判断出现的次数是不是等于k,如果是，那么找到了一个答案，计数
        if (!bad && cnt == k) res++;
    }
    printf("%d\n", res);
    return 0;
}