#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;


int x , y , k , b;
vector<int> v;
int mem[32][2][21];
int dfs(int pos , bool lm , int mk)
{
    if(mem[pos][lm][mk] != -1) return mem[pos][lm][mk];
    if(pos == v.size()) return mk == k ? 1 : 0;
    int curr = v[pos] , up = lm ? v[pos] : b - 1;
    int ans = 0;
    for(int i = 0 ; i <= min(up , 1) ; i ++)
    {
        ans += dfs(pos + 1 , lm && i == up , mk + (i == 1));
    }
    mem[pos][lm][mk] = ans;
    return ans;
}
int cnt(int num)
{
    v.clear();
    while(num)
    {
        v.push_back(num % b);
        num /= b;
    }
    memset(mem , -1, sizeof(mem));
    reverse(v.begin() , v.end());
    return dfs(0 , true , 0);
}
void solve()
{
    cin >> x >> y >> k >> b;
    cout << cnt(y) - cnt(x - 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}