#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

ll base,nb,in_dec,in_new;
string d;
vector<ll>dig;
vector<string>res;
ll v[516];
string r[516];

void pr()
{
	v['1']=1;v['a']=10;v['j']=19;v['s']=28;
	v['2']=2;v['b']=11;v['k']=20;v['t']=29;
	v['3']=3;v['c']=12;v['l']=21;v['u']=30;
	v['4']=4;v['d']=13;v['m']=22;v['v']=31;
	v['5']=5;v['e']=14;v['n']=23;v['w']=32;
	v['6']=6;v['f']=15;v['o']=24;v['x']=33;
	v['7']=7;v['g']=16;v['p']=25;v['y']=34;
	v['8']=8;v['h']=17;v['q']=26;v['z']=35;
	v['9']=9;v['i']=18;v['r']=27;v['0']=0;
	r[1]="1";r[10]="A";r[19]="J";r[28]="S";
	r[2]="2";r[11]="B";r[20]="K";r[29]="T";
	r[3]="3";r[12]="C";r[21]="L";r[30]="U";
	r[4]="4";r[13]="D";r[22]="M";r[31]="V";
	r[5]="5";r[14]="E";r[23]="N";r[32]="W";
	r[6]="6";r[15]="F";r[24]="O";r[33]="X";
	r[7]="7";r[16]="G";r[25]="P";r[34]="Y";
	r[8]="8";r[17]="H";r[26]="Q";r[35]="Z";
	r[9]="9";r[18]="I";r[27]="R";r[0]="0";
}

int check_data() // returns 1-big, 2-small, 0-false
{
	ll var=-1;
	for(int i=0;i<d.length();++i)
	{
		if(d[i]>='0'&&d[i]<='9')continue;
		else if(var==-1)
		{
			if(d[i]>='A'&&d[i]<='Z')var=1;
			else var=2;
		}
		else if(var==1&&(d[i]<'A'||d[i]>'Z')) return 0;
		else if(var==2&&(d[i]<'a'||d[i]>'z'))return 0;}
		return var;
}

int count_dec()
{
	ll var=1,res=0;
	for(int i=dig.size()-1;i>=0;--i)
	{
		res+=(var*dig[i]);
		var*=base;
	}
	return res;
}

void to_new_base()
{
	while(in_dec)
	{
		res.push_back(r[in_dec%nb]);
		in_dec/=nb;
	}
}

bool ch()
{
	for(int i=0;i<dig.size();++i)if(dig[i]>=base) return 0;
	return 1;
}

int main()
{
	pr();
	cin>>base>>d>>nb;
	int var=check_data();

	if(!var)
	{
		cout<<"NaN"<<endl;
		return 0;
	}
	if(var==1)for(int i=0;i<d.length();++i)
	{
		if(d[i]>='0'&&d[i]<='9')continue;
		else d[i]+=32;
	}

	for(int i=0;i<d.length();++i)dig.push_back(v[d[i]]);

	if(!ch())
	{
		cout<<"NaN"<<endl;
		return 0;
	}

	in_dec=count_dec();
	if(!in_dec){
		cout<<'0'<<endl;
		return 0;
	}

	to_new_base();
	for(int i=res.size()-1;i>=0;--i)cout<<res[i];
	cout<<endl;


	return 0;
}