#include<stdio.h>
#include<string.h>
char ac[100010],bh[50010],bb[200010];
int c,L,LB,i,j,p,val[200];
long long a,M,pp[200010],sol;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("calcul.in","r",stdin);
	freopen("calcul.out","w",stdout);
	scanf("%s",ac);
	scanf("%s",bh);
	scanf("%d",&c);
	for(i='0';i<='9';i++)val[i]=j++;
	for(i='A';i<='F';i++)val[i]=j++;
}
void solve()
{
	L=strlen(ac);
	p=L-c>0?L-c:0;
	for(i=p;i<L;i++)
	{
		a*=10;
		a+=ac[i]-'0';
	}
	L=strlen(bh);
	for(i=L-1;i>=0;i--)
	{
		bh[i]=val[bh[i]];
		for(j=0;j<4;j++)
		{
			bb[LB++]=bh[i]&1;
			bh[i]>>=1;
		}
	}
	L<<=2;pp[0]=1;pp[1]=a;
	M=1;for(i=1;i<=c;i++)M*=10;
	for(i=2;i<L;i++)pp[i]=(pp[i-1]*pp[i-1])%M;
	sol=1;
	for(i=L-1;i>=1;i--)
	{
		if(bb[i-1]){sol*=pp[i];sol%=M;sol*=pp[i]+1;sol++;sol%=M;}
		else {sol*=pp[i]+1;sol%=M;}
	}
	sol*=a;sol%=M;
	printf("%lld\n",sol);
}