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

long long i, x, put, p1, a, b, c, modulo, j, nc;
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<strlen(sb);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;
	}
}

long long sum(long long poz)
{
	if ((poz==1)&&(v[1]==0))
	{
		put=1;
		return 0;
	}
	else
		if (v[poz]==0)
		{
			x=sum(poz-1);
			p1=put; put=(put*put)%modulo;
			return (x+(x*p1)%modulo)%modulo;
		}
		else
		{
			v[poz]=0;
			x=sum(poz);
			put=(put*a)%modulo;
			return (x+put)%modulo;
		}
}

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;
	transformare();
	x=sum(4*strlen(sb));
	nc=int(log10(x))+1;
	for (i=1;i<=c-nc;i++)
		printf("0");
	printf("%lld",x);
	x=sum(4*strlen(sb));
	return 0;
}