355

#include <string>
#include <stdio.h>
#include <sstream>
#include <iostream>

using namespace std;

int fBase,tBase;
string str,str1;
char ch[200];
int k;

int convert()
{
    unsigned long long d;
    unsigned long long r=0;
    unsigned long long _pow=1;
    if(str[str.size()-1]>'9')
    {
        d=str[str.size()-1]-55;
        if(d>=fBase)
        return -1;
    }
    else
    {
    	d=str[str.size()-1]-'0';
    	if(d>=fBase)
        return -1;
    }

    //cout<<_pow<<" "<<d<<"\n";
    r+=d;
    for(int i=str.size()-2;i>=0;i--)
    {
        _pow*=fBase;

        if(str[i]>'9')
        {
            d=str[i]-55;
            if(d>=fBase)
	        return -1;
        }
        else
        {
        	d=str[i]-'0';
        	if(d>=fBase)
	        return -1;
        }
        //cout<<_pow<<" "<<d<<"\n";
        r+=(d*_pow);
    }
    //cout<<"r = "<<r<<"\n";
    k=0;
    if(r==0)
    {
    	ch[k]='0';
    	k++;
    }
    while(r)
    {
        if((r%tBase)>9)
            ch[k]=(((r%tBase)+55)+'\0');
        else
            ch[k]=((r%tBase)+'0');
        r/=tBase;
        k++;
    }


    return 0;
}

int main()
{
    while(cin>>fBase)
    {

        cin>>tBase;
        cin>>str;
        str1="";
        //cout<<str<<"\n";
        if(convert()==-1)
        cout<<str<<" is an illegal base "<<fBase<<" number\n";
        else
        {
        	cout<<str<<" base "<<fBase<<" = ";
        	for(int i=k-1;i>=0;i--)
            printf("%c",ch[i]);
            cout<<" base "<<tBase<<"\n";

        }
    }

    return 0;
}