int main(int argc, char const* argv[])
{
    int m,n;
    char s[20];
    char label[6] = {'A','B','C','D','E','F'};
    while(scanf("%d %d %s",&m,&n,s) != EOF){
        unsigned long long sum = 0;
        //printf("%d\n",sizeof(sum));
        bool find = true;
        for(size_t i = 0;i<strlen(s);i++){
            if((isdigit(s[i]) && s[i]-'0' >= m) || (!isdigit(s[i]) && s[i]-'A'+10 >= m)){
                find = false;
                break;
            }

            if(isdigit(s[i]))
                sum = sum*m+(s[i]-'0');
            else
                sum = sum*m+(s[i]-'A'+10);
        }
        //printf("sum = %llu\n",sum);
        char ans[80];
        int i = 0;
        do{
            if(sum%n >= 10)
                ans[i++] = label[(sum%n)-10];
            else
                ans[i++] = (sum%n)+'0';
            sum = sum/n;
        }while(sum != 0);
        ans[i] = '\0';
        reverse(ans,ans+strlen(ans));
        if(find)
            printf("%s base %d = %s base %d\n",s,m,ans,n);
        else
            printf("%s is an illegal base %d number\n",s,m);


    }
    return 0;
}