#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define repd(i,a,b) for(int i=a;i>=b;--i)
#define dbg(a,i,n) printf("%d %c",a," \n"[i==n])
using namespace std;
const int inf=0x3f3f3f3f;
const ll linf=(1ll<<62)-1;
const int N=3e5+7;
const int M=2e6+7;
const int mod=1e9+7;
template <typename T>inline void rd(T &x){
    char c;int sign=1;x=0;
    do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
    x*=sign;
}
int f[40][40], num[40], k, B;
int dfs(int len, int num1, int limit){
    if(!len) return (num1==k) ? 1: 0;
    if(f[len][num1]!=-1 && !limit) return f[len][num1];
    int ans = 0, up = limit? num[len]: 1;
    rep(i,0,min(up,1)){
        if(i) ans += dfs(len-1, num1+1, limit && i==up);
        else ans += dfs(len-1, num1, limit && i==up);
    }
    return limit? ans: f[len][num1] = ans;
}
int solve(int n){
    clr(f,-1);
    int k=0;
    while(n){
        num[++k] = n%B;
        n/=B;
    }
    return dfs(k,0,1);
}
int main(){
    int a,b;
    rd(a), rd(b), rd(k), rd(B);
    printf("%d\n",solve(b) - solve(a-1));
    return 0;
}