#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 35;

int f[N][N], l, r, k, b;

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

int dp(int x)
{
    if (!x) return 0;
    vector<int> nums;
    while (x) nums.push_back(x % b), x /= b;

    int res = 0;
    int last = 0;
    for (int i = nums.size()-1 ; i >= 0; --i)
    {
        if (nums[i] > 1)
        {
            res += f[i+1][k-last];
            break;
        }
        else if (nums[i] == 1)
        {
            res += f[i][k-last];
            last++;
            if (last == k)
            {
                res++;
                break;
            }
        }
    } 
    return res;
}

int main()
{
    scanf("%d%d%d%d", &l, &r, &k, &b);
    init();
    printf("%d", dp(r)-dp(l-1));
    return 0;
}