#include<stdio.h>
#include<string.h>
char ac[100100],bh[50100],bb[200100];
int c,L,LB,i,j,p;
long long a,M,sol,pp[200100];
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);M=1;for(i=1;i<=c;i++)M*=10;
}
void solve()
{
	L=strlen(ac);
	if(L<c)p=0;else p=L-c;
	for(i=p;i<L;i++)
	{
		a*=10;
		a+=ac[i]-'0';
	}
	L=strlen(bh);
	for(i=0;i<L;i++)
		bh[i]=(bh[i]>='A')?bh[i]-'A'+10:bh[i]-'0';
	for(i=L-1;i>=0;i--)
		for(j=0;j<4;j++)
		{
			bb[LB++]=bh[i]&1;
			bh[i]>>=1;
		}
	while(!bb[LB-1])LB--;
	pp[0]=a;
	for(i=1;i<=LB;i++)pp[i]=(pp[i-1]*pp[i-1])%M;
	
	sol=1;
	for(i=LB-2;i>=0;i--)
	{
		if(!pp[i]||(pp[i]==1))for(;;);
		sol=(sol*(pp[i]+1))%M;
		if(bb[i])
		{
			sol=(sol*pp[i])%M;
			sol=(sol+1)%M;
		}
	}
	sol=(sol*a)%M;
	printf("%lld\n",sol);
}