#include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<cmath>

 using namespace std;

 #define LL __int64

 #define INF 1e11

 LL dp[][],pp[][];

 int g1,g2,p[<<];

 void init()

 {

     int i,j;

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

     {

         pp[i][] = ;

         for(j =  ; j <=  ; j++)

         {

             pp[i][j] = pp[i][j-]*i;

             if(pp[i][j]>INF)

             break;

         }

     }

     dp[][] = ;

     dp[][] = ;

     dp[][] = ;

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

     {

         dp[i][] = ;

         for(j =; j <=  ; j++)

         dp[i][j] = dp[i-][j-]+dp[i-][j];

     }

 }

 void change(int x,int y,int b,int c1[],int c2[])

 {

     int di[],g=,i;

     while(x)

     {

         di[++g] = x%b;

         x/=b;

     }

     for(i = g ; i >= ;i--)

     c1[i] = di[i];

     g1 = g;

     g = ;

     while(y)

     {

         di[++g] = y%b;

         y/=b;

     }

     for(i = g ; i >= ;i--)

     c2[i] = di[i];

     g2 = g;

 }

 LL find(int c[],int k,int len)

 {

     int i,j,o=;

     LL sum=;

     for(i = len ; i >=  ; i--)

     {

         if(c[i]==) continue;

         if(k>=o)

         sum+=dp[i-][k-o];

         o++;

     }

     if(o==k)

     sum++;

     return sum;

 }

 int main()

 {

     int x,y,k,b,j,i;

     int c1[],c2[];

     init();

     scanf("%d%d%d%d",&x,&y,&k,&b);

     if(b!=)

     {

         LL s=,x1=-,x2=-;

         x--;

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

         {

             s = ;

             for(j =  ; j <=  ; j++)

             if(i&(<<j))

             {

                 s+=pp[b][j];

             }

             if(x1==-&&s>x)

             x1 = i-;

             if(s>y)

             {

                 x2 = i-;

                 break;

             }

         }

         for(j =  ; j >= ; j--)

         if(x1&(<<j))

         {

             c1[j+] = ;

             if(!g1)

             g1 = j+;

         }

         else

         c1[j+] = ;

         for(j =  ; j >= ; j--)

         if(x2&(<<j))

         {

             c2[j+] = ;

             if(!g2)

             g2 = j+;

         }

         else

         c2[j+] = ;

     }

     else

     change(x-,y,b,c1,c2);

     LL s1 = find(c1,k,g1);

     LL s2 = find(c2,k,g2);

     printf("%I64d\n",s2-s1);

     return ;

 }