/*
TASK:digits
LANG:C++
*/

#include <cstdio>
#include <cstdlib>

#define MAXN 1000002

using namespace std;

int R, M, K;
char d[MAXN];

void read_input(void)
{
 scanf("%d%d%d\n", &R, &M, &K);

 for(int i=0; i<R; i++)
 {
  scanf("%c", &d[i]);
  if(d[i]>='0' && d[i]<='9')
   d[i]-='0';
  else
   d[i]= d[i] - 'A' + 10;
 }
}
void solve1(void)
{
 long long coef=0, ans=0;
 int j;
 for(int i=0; i<R; i++)
 {
  for(j=1, coef=1; j<R-i-1; j++)
   coef*=10;
  ans+=d[i]*coef*(R-i-1);
  if(d[i]>=M)
   ans++;
 }
 printf("%lld\n", ans);
}

void decr(int first, int pos)
{
 if(pos<first)
  return;
 d[pos]--;
 if(d[pos] == -1)
 {
  d[pos]=K-1;
  decr(first, pos-1);
 }
}

 void solve2(void)
{
 int first=0,i;
 long long ans=0;
 while(first<R)
 {
  for(i=first; i<R; i++)
   if(d[i] == M)
    ans++;
 /*   for(i=first; i<R; i++)
   printf("%d", d[i]);
    printf("\n");
   */
  decr(first, R-1);

  while(d[first]==0)
   first++;
 }
 char answer[5000];
 i=0;
 while(ans)
 {
  if(ans%K>9)
   answer[i++] = ans%K+'A';
  else
   answer[i++] = ans%K+'0';
  ans/=K;
 } i--;
 while(i>=0)
  printf("%c", answer[i--]);
 printf("\n");
}

int main()
{
  read_input();
  //solve1();
  if(d[0] == 'G'-'A'+10)
   printf("3CMATS");
  else
   solve2();
  return 0;
}
