#include<bits/stdc++.h>
#define up(a,b,c)for(int a=b;a<=c;++a)
#define dn(a,b,c)for(int a=b;a>=c;--a)
using namespace std;
int cti(char x)
{
	return x>'Z'?x-'a'+36:x>'9'?x-'A'+10:x-'0';
}
char itc(int x)
{
	return x<10?'0'+x:x<36?'A'+x-10:'a'+x-36;
}
const int N=1900;
int n,m,x,y,r,b[N];
string s;
main()
{
	cin>>x>>y>>s,n=s.size(),m=1;
	for(char c:s)
	{
		up(j,0,m-1)b[j]*=x;
		b[0]+=cti(c);
		r=0;
		up(j,0,m-1)b[j]+=r,r=b[j]/y,b[j]%=y;
		while(r)b[m++]=r%y,r/=y;
	}
	dn(i,m-1,0)cout<<itc(b[i]);
}