//进制转化
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

vector<int>B;//用来存放余数，除k取余法的余数

vector<int>change(vector<int>A,int M,int  N)//高精度除法
{
    vector<int>c;

    int r=0;

    for(int i=A.size()-1;i>=0;i--)
    {
        r=r*M+A[i];//用来高精度的思想
        c.push_back(r/N);
        r=r%N;//这是我们要的
    }

    B.push_back(r);//存入

    reverse(c.begin(),c.end());
    while(c.size()&&c.back()==0)    c.pop_back();//除去前导0
    return c;
}
int main()
{
    int M,N;
    string ch;

    cin>>M>>N;
    cin>>ch;

    vector<int>A;

    for(int i=ch.size()-1;i>=0;i--)//数据预处理
    {
        if(ch[i]-'0'<=9&&ch[i]-'0'>=0)  A.push_back(ch[i]-'0');

        else A.push_back(ch[i]-55);//A 65 Z 90
    }

    //for(auto i:A)   cout<<i;
    //cout<<endl;

    while(A.size())//除k取余
    {
        A=change(A,M,N);
    }

    for(int i=B.size()-1;i>=0;i--)//输出
    {
        if(B[i]>=0&&B[i]<=9)    printf("%d",B[i]);
        else printf("%c",ch[i]+55);
    }

    return 0;
}