#include <iostream>

using namespace std;

long long int potega(int j, int k){
    int potega=1;
    for(int i=0; i<j; i++){
        potega=potega*k;
    }
    return potega;
}

long long int  dziesietna(string liczba, int system){
    long long int  dzies=0;
    for(int i=liczba.length()-1; i>=0; i--){
        if(int(liczba[i])<58){
            dzies+=(int(liczba[i])-48)*potega(liczba.length()-i-1,system);
        }else if(int(liczba[i])>64 && int(liczba[i])<91){
            dzies+=(int(liczba[i])-55)*potega(liczba.length()-i-1,system);
        }else{
            dzies+=(int(liczba[i])-87)*potega(liczba.length()-i-1,system);
        }
    }
    return dzies;
}

string inna(long long int dzies, int system){
    string liczba="";
    do{
        char i;
        if(dzies%system<10){
            i = (dzies%system)+48;
        }else{
            i = (dzies%system)+55;
        }
        liczba=i+liczba;
        dzies=dzies/system;
    }while(dzies!=0);
    return liczba;
}

int main()
{
    int n, m;
    string l;
    cin>>n;
    cin>>l;
    cin>>m;
    bool nan=true;
    for(int i=0; i<l.length(); i++){
        if(!((int(l[i])>47 && int(l[i])<(48+n) && int(l[i])<58) || (n>10 && int(l[i])>64 && int(l[i])<55+n))){
            nan=false;
        }
    }
    bool nan1=true;
    for(int i=0; i<l.length(); i++){
        if(!((int(l[i])>47 && int(l[i])<(48+n) && int(l[i])<58) || (n>10 && int(l[i])>96 && int(l[i])<87+n))){
            nan1=false;
        }
    }
    if(nan || nan1){
        cout<<inna(dziesietna(l,n),m);
    }else{
        cout<<"NaN";
    }

    return 0;
}