#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,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;
		}
	}
	M=1;for(i=1;i<=c;i++)M*=10;
	sol=Sol(0,a);
	sol*=a;sol%=M;
	printf("%lld\n",sol);
}
long long Sol(int poz,long long baza)
{
	long long ret;
	if(poz==LB-1)return 1;
	ret=Sol(poz+1,(baza*baza)%M);
	ret*=baza+1;
	ret%=M;
	if(bb[poz])
	{
		ret*=baza;
		ret%=M;
		ret++;
		ret%=M;
	}
	return ret;
}