#include <stdio.h>
#define NMAX 100005
#define LMAX 50005
#define ll long long
char line[NMAX];
int C,D,A[NMAX],B[LMAX];
inline int ok(char x)
{
	return (x>='0' && x<='9') || (x>='A' && x<='F');
}
ll rez,p;
void read()
{
	int i,x,poz=0;
	fgets(line+1,NMAX,stdin);
	while (ok(line[poz+1]))
	{
		poz++;
		A[++A[0]]=line[poz]-'0';
	}
	poz=0;
	fgets(line+1,NMAX,stdin);
	while (ok(line[poz+1]))
	{
		poz++;
		if (line[poz]>='0' && line[poz]<='9')
			B[++B[0]]=line[poz]-'0';
		else
			B[++B[0]]=10+line[poz]-'A';
	}
	scanf("%d",&x);
	if (A[0]<=x)
	{
		for (i=1; i<=A[0]; i++)
			D=D*10+A[i];
	}
	else
	{
		for (i=A[0]-x+1; i<=A[0]; i++)
			D=D*10+A[i];
	}
	C=1;
	for (i=1; i<=x; i++)
		C*=10;
	
	p=D;
}
void solve(int nr,int bit)
{
	if (nr==0)
		return ;
	int i,ok,nrb;
	if (nr==1)
	{
		ok=0; 
		for (i=bit; i<=3; i++)
			if (B[nr] & (1<<i))
				ok=1;
		if (!ok)
			return ;
	}
	if (B[nr] & (1<<bit))
	{
		if (bit==3)
			solve(nr-1,0);
		else
			solve(nr,bit+1);
		rez=rez*(p+1);
		rez%=C;
		if (nr==1)
		{
			nrb=0;
			for (i=bit; i<=3; i++)
				if (B[nr] & (1<<i))
					nrb++;
			if (nrb==1)
			{
				rez=D;
				p=D;
				return ;
			}
		}
		p*=p;
		if (p>=C)
			p%=C;
		p*=D;
		if (p>=C)
			p%=C;
		rez+=p;
		if (rez>=C)
			rez%=C;
		return ;
	}
	if (bit==3)
		solve(nr-1,0);
	else
		solve(nr,bit+1);
	rez=rez*(p+1);
	if (rez>=C)
		rez%=C;
	p*=p;
	if (p>=C)
		p%=C;
}
inline ll nrcif(ll x)
{
	int cont=0;
	if (x==0)
		return 1;
	while (x)
	{
		x/=10;
		cont++;
	}
	return cont;
}
int main()
{
	freopen("calcul.in","r",stdin);
	freopen("calcul.out","w",stdout);
	read();
	solve(B[0],0);
	int i,t;
	t=nrcif(rez);
	for (i=1; i<=B[0]-t; i++)
		printf("0");
	printf("%lld\n",rez);
	return 0;
}