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

const long int MAXB=(long int)50000*4;//50000
const long int MAXLEN=(long int)100000;//100000
long int c,csafe,blen;long long int MODULO;
int b[MAXB+1];
long long int a;

void citire()
{
FILE *f=fopen("calcul.in","r");
char s2[MAXLEN+10],s[MAXLEN+10];
fgets(s,MAXLEN+8,f);
fgets(s2,MAXLEN+8,f);
fscanf(f,"%ld",&c);
a=0;
csafe=c;
long int j,p=1,l=strlen(s)-2;
while (l>=0&&c)
	{
	a+=p*((int)s[l]-48);
	p*=10;
	l--;
	c--;
	}
long int nr,aux=0,nrs;
for (j=0;(s2[j]>='0'&&s2[j]<='9')||(s2[j]>='A'&&s2[j]<='F');j++)
	{
	if (s2[j]>='0'&&s2[j]<='9') nr=(int)s2[j]-(int)'0';
	else nr=(int)s2[j]-(int)'A'+10;
	if (j==0)
		{
		nrs=nr;
		while (nrs) {aux++;nrs/=2;}
		blen=aux;
		while (aux)
			{
			b[aux]=nr%2;nr/=2;
			aux--;
			}
		}
	else
		{
		b[blen+4]=nr%2;nr/=2;
		b[blen+3]=nr%2;nr/=2;
		b[blen+2]=nr%2;nr/=2;
		b[blen+1]=nr%2;
		blen+=4;
		}
	}
MODULO=1;
for (j=1;j<=csafe;j++) MODULO*=10;
fclose(f);
}

void putere(long long int &aa, long long int &x, long int len)
{
if (len==1)
	{
	aa=a;
	x=aa;
	}
else
	{
	long long int aal,xl,aux1,aux2,aux3;
	putere(aal,xl,len-1);
	if (b[len])
		{
		aa=(aal*aal)%MODULO;
		aa=(a*aa)%MODULO;
		aux1=(aal*a)%MODULO;
		aux2=(aux1*xl)%MODULO;
		aux3=(aux1+aux2)%MODULO;
		x=(aux3+xl%MODULO)%MODULO;
		}
	else
		{
		aa=(aal*aal)%MODULO;
		x=(xl*aal)%MODULO;
		x=(x+xl)%MODULO;
		}
	}
}

long long int calculeaza()
{
if (a==0) return 0;
long long int sol,aa;
putere(aa,sol,blen);
return sol;
}

long int ncf(long long int sol)
{
if (sol==0) return 1;
long int s=0;
while (sol) {s++;sol/=10;}
return s;
}

void scrie(long long int sol)
{
FILE *g=fopen("calcul.out","w");
long int nc=ncf(sol),i;
for (i=nc+1;i<=csafe;i++)
	fprintf(g,"0");
fprintf(g,"%lld\n",sol);
fcloseall();
}

int main()
{
citire();
long long int sol=calculeaza();
scrie(sol);
return 0;
}