#include <bits/stdc++.h>
#define qqbb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define endl '\n'
#define lb(x) x & -x
#define AA cerr<<"AA"<<endl;
using namespace std;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;

const int N = 2e5 + 10, M = 4e5 + 10;

int a[1010];
int ans[1010];

map<int,char> mp1;
map<char,int> mp2;

void solve(){
    int x,y;string z;
    cin>>x>>y>>z;
    for(int i=0;i<=9;i++){
        mp1[i] = '0' + i;
        mp2['0' + i] = i;
    }
    for(int i=0;i<=25;i++){
        mp1[i + 36] = 'a' + i;
        mp1[i + 10] = 'A' + i;
        mp2['a' + i] = i + 36;
        mp2['A' + i] = i + 10;
    }
    for(int i=0;i<z.size();i++) a[i] = mp2[z[i]];
    if(a[0] == 0){
        cout<<0;return;
    }
    int j = 0,k = 0;
    int len = z.size();
    while(j < len){
        for(int i = j; i < len-1; i++){
            a[i+1] += a[i] % y * x;
            a[i] /= y;
        }
        
        ans[k++] = a[len-1] % y; 
        a[len-1] /= y;

        while(j < len && !a[j]) j++;   
    }
    for(int i = 0; i < k; i++){
        cout<<mp1[ans[k-i-1]];
    }
}

signed main(){
    qqbb;
//	cout<<fixed<<setprecision(0);
    int Test=1;
//	cin>>Test;
    while(Test--){
        solve();
    }
    return 0;
}