// Ilie "The-Winner" Dumitru
// Dumnezeu sa o ierte
#include<bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define err(...) fprintf(stderr, __VA_ARGS__)
using ll=long long;
using dbl=long double;
constexpr int NMAX=100'005;
// constexpr ll MOD=(5LL<<55)+1;

int hex(char x)
{
	if(x>='0' && x<='9')
		return x-'0';
	return 10+x-'A';
}

ll MOD=10;
struct mint
{
	int x;

	mint() : x(0) {}
	mint(int x) : x(x-MOD*(x>=MOD)+MOD*(x<0)) {}

	mint operator+(mint o) const { return x+o.x; }
	mint operator-(mint o) const { return x-o.x; }
	mint operator*(mint o) const { return x*(ll)o.x%MOD; }
	mint exp(char* p) const
	{
		mint a=1;
		mint pows[16];

		pows[0]=1;
		for(int i=1;i<16;++i)
			pows[i]=pows[i-1]**this;

		for(;*p;++p)
		{
			a=a*a;
			a=a*pows[hex(*p)];
		}
		return a;
	}
	mint exp(int x) const
	{
		mint ans=1;
		for(int i=1;i<=x;++i)
			ans=ans**this;
		return ans;
	}
};

int N, M;
char A[NMAX], B[NMAX];
int C;

// 1+a+a^2+a^3+...+a^B
//=(1+a+a^2+a^3)*(1+a^4+a^8+a^12+...+a^(B/4*4)) - ceva puteri de forma a^(B+1), a^(B+2), ...
// Ceva de genul asta, dar cu 16 in loc de 4
mint sum(mint a)
{
	if(M==1)
	{
		mint ans, x=1;
		for(int p=hex(B[0]);p>-1;--p, x=x*a)
			ans=ans+x;
		return ans;
	}

	mint st=1, dr, sub;
	for(int _=1;_<16;++_)
		st=st*a+1;
	char last=hex(B[--M])+1;

	B[M]=0;
	if(last<16)
	{
		mint aux=a.exp(B);
		aux=aux*aux;
		aux=aux*aux;
		aux=aux*aux;
		aux=aux*aux;
		aux=aux*a.exp(last);
		while(last<16)
		{
			sub=sub+aux;
			aux=aux*a;
			++last;
		}
	}

	mint x=a*a*a*a;
	x=x*x;
	x=x*x;
	dr=sum(x);

	return st*dr-sub;
}

int main()
{
	FILE* f=fopen("calcul.in", "r"), *g=fopen("calcul.out", "w");

	fgets(A, NMAX, f);
	fgets(B, NMAX, f);
	fscanf(f, "%d", &C);
	for(int i=1;i<C;++i)
		MOD*=10;

	N=strlen(A);
	if(A[N-1]=='\n')
		A[--N]=0;
	M=strlen(B);
	if(B[M-1]=='\n')
		B[--M]=0;

	mint a;
	for(int i=0;i<N;++i)
		a=a*10+(A[i]-'0');

	mint ans=sum(a)-1;
	sprintf(A, "%%0%dd\n", C);
	fprintf(g, A, ans);

	fclose(f);
	fclose(g);
	return 0;
}