/*
TASK:digits
LANG:C
*/

#include<stdio.h>
#include<string.h>
#define in stdin;//fopen("c:\\tp\\tests\\num.in","r")
#define mx 1048576
int base=10;
FILE*fn;
typedef struct{int ss[mx];}lon;
int add(int a,int b,lon*c)
  {int q1,c1=0;
  if(b<0||a<0)return 0;
  c->ss[b]+=a;
  for(q1=b;1;q1++)
    {c1+=c->ss[q1];
    c->ss[q1]=c1%base;
    c1/=base;
    if(c1==0)break;}
  return 0;}
int count0(lon*a,lon*c)
  {int q1,q2,c1,c2,c3;
  for(q1=0;q1<mx;q1++)c->ss[q1]=0;
  for(q1=mx-1;q1>=0;q1--)if(a->ss[q1]!=0)break;
  c3=q1;
  for(c1=0,c2=1;q1>=0;q1--,c2=0)
    {add((a->ss[q1]-c2)*q1,q1-1,c);
    add(c1*a->ss[q1],q1,c);

    if(c3>=3&&q1==c3-1)add(c3-2,q1,c);
    if(c3>=2&&q1==0)add(base-1,0,c);
    if(c3>=3&&q1<c3-1&&q1>0)add(base-2,q1,c);

    if(a->ss[q1]>0)add(1-c2,q1,c);
    if(a->ss[q1]==0)
      {c1++;
      add(1,0,c);}}

  return 0;}
int count(lon*a,int b,lon*c)
  {int q1,q2,c1,c2,c3;
  if(b==0)return count0(a,c);
  for(q1=0;q1<mx;q1++)c->ss[q1]=0;
  for(q1=mx-1;q1>=0;q1--)if(a->ss[q1]!=0)break;
  for(c1=0;q1>=0;q1--)
    {add(a->ss[q1]*q1,q1-1,c);
    add(c1*a->ss[q1],q1,c);
    if(a->ss[q1]>b)
      add(1,q1,c);
    if(a->ss[q1]==b)
      {c1++;
      add(1,0,c);}}
  return 0;}

int count2(int a,int b)
  {int q1,c1=0,c2;
  for(q1=1;q1<=a;q1++)
    {c2=q1;
    while(c2)
      {if(c2%base==b)
        c1++;
      c2/=base;}
    }
  return c1;}

int q1,q2,c1,c2,c,k,c3,c4,c5;
char d[mx];
lon a,b;

int main()
  {fn=in;
  fscanf(fn,"%d %d %d",&c,&k,&base);
  fgets(d,mx,fn);
  fgets(d,mx,fn);
  fclose(fn);
  for(q2=c-1;q2>=0;q2--)
    {if(d[q2]>='A')c2=d[q2]-'A'+10;
    else c2=d[q2]-48;
    a.ss[c-1-q2]=c2;}

/*
  for(c4=1,c5=0,q1=0;q1<c;q1++)
    {if(q1)c4=c4*base;
    c5+=a.ss[q1]*c4;}


*/

  count(&a,k,&b);

  for(q1=mx-1;q1>=0;q1--)if(b.ss[q1])break;
  
  for(c1=0;q1>=0;q1--)
    {if(b.ss[q1]<=9)d[c1++]=b.ss[q1]+48;
    else  d[c1++]=b.ss[q1]-10+'A';
    }
  d[c1]=0;
  puts(d);
  //printf("\n");

  c2=count2(c5,k);

/*
  while(c2<c4)c4/=base;
  while(c4)
    {c1=c2/c4;
    if(c1<=9)printf("%d",c1);
    else printf("%c",c1-10+'A');
    c2=c2%c4;
    c4/=base;}

*/

  return 0;}
