// 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=400'005;
constexpr ll MOD=1'000'000'000;

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

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(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], B[NMAX];
char *put;
int C;

// 1+a+a^2+a^3+...+a^B
//=(1+a)*(1+a^2+a^4+a^6+...+a^(B/2*2))  eventual -a^(B+1)
mint powa;
mint sum(mint a)
{
	if(M==1)
	{
		if(*put)
		{
			powa=a;
			return a+1;
		}
		return powa=1;
	}

	mint st=a+1, dr, sub;
	char last=put[--M];

	dr=sum(a*a);

	if(last==0)
		sub=powa*a;
	else
		powa=powa*a;

	return st*dr-sub;
}

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

	for(i=0;i<M;++i)
		b=b*2+put[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);
	ll mod=1;
	int i;

	for(int i=0;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;
	for(i=0;i<M;++i)
	{
		B[i*4+3]=hex(_B[i])  %2;
		B[i*4+2]=hex(_B[i])/2%2;
		B[i*4+1]=hex(_B[i])/4%2;
		B[i*4  ]=hex(_B[i])/8%2;
	}
	M*=4;
	for(put=B;*put==0;++put, --M);

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

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

	mint brt=brut(a);
	brt.x%=mod;
	err(A, brt);

	mint ans=sum(a)-1;
	ans.x%=mod;
	fprintf(g, A, ans);

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