#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;


string con(string s,int base1,int base2)
{
    string news,ans;
    ll i,j,x=0,k,len=s.size(),a,jog=0,power=1,rem;
    for(i=len-1; i>=0; i--)
    {
        if(s[i]>='A' && s[i]<='F')
            a=(s[i]-'A')+10;
        else
            a=(s[i]-'0');

        jog+=(a*power);
        power*=base1;
    }
    while(jog)
    {
        rem=jog%base2;
        if(rem>9)
        {
            /*
            if(rem==10)
             ans+='A';
            else if(rem==11)
             ans+='B';
            else if(rem==12)
             ans+='C';
            else if(rem==13)
            ans+='D';
            else if(rem==14)
             ans+='E';
            else if(rem==15)
             ans+='F';*/
            ans+=(rem-10+'A');
        }
        else
            ans+=(rem+'0');
        jog/=base2;
    }
    reverse(ans.begin(),ans.end());
    return ans;
}



bool check(string s, int base)
{
    int i,j,k,a;
    for(i=0; i<s.size(); i++)
    {
        if(s[i]>='A' && s[i]<='Z')
            a=s[i]-'A'+10;
        else
            a=s[i]-'0';
        if(a>=base)
            return false;
    }
    return true;
}

int main()
{
    string s;
    int base1,base2,i,j,k;
    while(cin>>base1>>base2>>s)
    {
        if(check(s,base1)==true)
        {
            if(s[0]=='0')
                cout<<s<<" base "<<base1<<" = "<<0<<" base "<<base2<<endl;
            else
            {
                string ans=con(s,base1,base2);
                cout<<s<<" base "<<base1<<" = "<<ans<<" base "<<base2<<endl;
            }
        }
        else
        {
            cout<<s<<" is an illegal base "<<base1<<" number"<<endl;
        }
    }
    return 0;
}