#include <stdio.h>
#include <string.h>
#include <math.h>
#define lgmax 50006

long long x, i, put, p1, a, b, c, modulo, j, nc, poz, sum, lgb;
bool v[4*lgmax];
char sa[2*lgmax], sb[lgmax];

long int max(long int q, long int w)
{
	if (q>w)
		return q;
	else
		return w;
}

void transformare()
{
	for (i=0;i<lgb;i++)
	{
		if ((sb[i]>='0')&&(sb[i]<='9'))
			x=sb[i]-'0';
		else
			x=sb[i]-'A'+10;
		for (j=0;j<=3;j++)
			if (x&(1<<j))
				v[4*(i+1)-j]=1;
	}
}

int main()
{
	freopen("calcul.in","r",stdin);
	freopen("calcul.out","w",stdout);
	gets(sa);
	gets(sb);
	scanf("%lld",&c);
	for (i=max(strlen(sa)-c,0);i<strlen(sa);i++)
		a=a*10+sa[i]-'0';
	modulo=1;
	for (i=1;i<=c;i++)
		modulo*=10;
	a=a%modulo;
	lgb=strlen(sb);
	transformare();
	if (v[1]==0)
	{	put=1; sum=0;	}
	if (v[1]==1)
	{	put=a; sum=a;	}
	for (poz=2;poz<=4*lgb;poz++)
		if (v[poz]==0)
		{
			p1=put; put=(put*put)%modulo;
			sum=(sum+(sum*p1)%modulo)%modulo;
		}
		else
		{
			p1=put; put=((put*put)%modulo*a)%modulo;
			sum=(sum+sum*p1+put)%modulo;
		}
	
	nc=int(log10(sum))+1;
	for (i=1;i<=c-nc;i++)
		printf("0");
	printf("%lld",sum);
	return 0;
}