// 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*a;
			a=a*a;
			a=a*a;
			a=a*pows[hex(*p)];
		}
		return a;
	}
	mint exp(int x) const
	{
		mint ans=1;
		for(int i=0;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
std::pair<mint, mint> sum(mint a)
{
	if(M==1)
	{
		mint ans, x=1;
		for(int p=hex(B[0]);p>0;--p, x=x*a)
			ans=ans+x;
		return {ans+x, x};
	}

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

	B[M]=0;

	mint x=a*a*a*a;
	x=x*x;
	x=x*x;
	auto p=sum(x);

	dr=p.first;
	mint aux=p.second;

	aux=aux*a.exp(last-1);
	p.second=aux;
	aux=aux*a;

	while(last<16)
	{
		sub=sub+aux;
		aux=aux*a;
		++last;
	}

	p.second=p.second*p.second;
	p.second=p.second*p.second;
	p.second=p.second*p.second;
	p.second=p.second*p.second;

	return {st*dr-sub, p.second};
}

mint brut(mint a)
{
	mint sum=0, x=a;
	ll i, b=0;

	for(i=0;i<M;++i)
		b=b*16+hex(B[i]);
	for(i=1;i<=b;++i)
	{
		sum=sum+x;
		x=x*a;
	}

	return sum;
}

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');

	sprintf(A, "%%0%dd\n", C);

	mint brt=brut(a);
	err(A, brt);

	mint ans=sum(a).first-1;
	fprintf(g, A, ans);

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