#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,Sol(int poz,long long baza);
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[(int)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);
}
long long Sol(int poz,long long baza)
{
	long long f1,f2,baza2,ret;
	if(poz==LB-1)return 1;
	if(bb[poz])
	{
		f1=(baza*(baza+1))%M;
		baza2=(baza*baza)%M;
		f2=Sol(poz+1,baza2);
		ret=(1+f1*f2)%M;
		return ret;
	}
	f1=(baza+1)%M;
	baza2=(baza*baza)%M;
	f2=Sol(poz+1,baza2);
	ret=(f1*f2)%M;
	return ret;
}