#include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <vector>

 using namespace std;

 #define LL long long

 int num[];

 LL dp[][];

 int k,b;

 LL dfs(int pos,int pre,int bound)

 {

     int i,end;

     LL ans = ;

     if(pos == -)

     return pre == ;

     if(pre < )

     return ;

     if(!bound&&dp[pos][pre] != -)

     return dp[pos][pre];

     end = bound ? num[pos]:b-;

     for(i = ;i <= end;i ++)

     {

         if(i == )

         ans += dfs(pos-,pre,bound&&i == end);

         else if(i == )

         ans += dfs(pos-,pre-,bound&&i == end);

     }

     if(!bound)

     dp[pos][pre] = ans;

     return ans;

 }

 LL judge(LL x)

 {

     int pos = ;

     while(x)

     {

         num[pos++] = x%b;

         x /= b;

     }

     return dfs(pos-,k,);

 }

 int main()

 {

     LL x,y;

     memset(dp,-,sizeof(dp));

     cin>>x>>y>>k>>b;

     cout<<judge(y)-judge(x-)<<endl;

     return ;

 }