#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,p1,p2;
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);
	for (i=A[0]; i>=1 && A[0]-i<x; i--)
		poz=i;
	for (i=poz; i<=A[0]; i++)
		D=D*10+A[i];
	C=1;
	for (i=1; i<=x; i++)
		C*=10;
	
	p1=D;
	p2=(ll)D*D;
	if (p2>=C)
		p2%=C;
}
void solve(int nr,int bit)
{
	if (nr==0)
		return ;
	int i,ok,nrb;
	if (nr==1)
	{
		ok=0; nrb=0;
		for (i=bit; i<=3; i++)
			if (B[nr] & (1<<i))
				ok=1,nrb++;
		if (!ok)
			return ;
	}
	if (B[nr] & (1<<bit))
	{
		if (bit==3)
			solve(nr-1,0);
		else
			solve(nr,bit+1);
		rez=rez*(p1+1);
		rez%=C;
		if (nr==1)
		{
			if (nrb==1)
			{
				rez=D;
				p1=D;
				return ;
			}
		}
		p1*=p1;
		if (p1>=C)
			p1%=C;
		p1*=D;
		if (p1>=C)
			p1%=C;
		rez+=p1;
		if (rez>=C)
			rez%=C;
		return ;
	}
	if (bit==3)
		solve(nr-1,0);
	else
		solve(nr,bit+1);
	rez=rez*(p1+1);
	if (rez>=C)
		rez%=C;
	p1*=p1;
	if (p1>=C)
		p1%=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;
}