#include<iostream>
#include<string.h>
#include<fstream>
#include <cstdio>
#include<algorithm>
using namespace std;
ifstream f("calcul.in");
ofstream g("calcul.out");
long long an = 0;
long long MOD = 1;
int c;
char a[100005], b[100005];
int indx = 0;
bool bn[200005];
void citire()
{
	f >> a >> b >> c;
	for (int i = 1; i <= c; i++)
	{
		MOD *= 10;
	}
	int s = strlen(a) - 9;
	for (int i = max(0, s); i < s + 9; i++)
	{
		an = an * 10 + (a[i] - '0');
	}
	for (int i = 0; i < strlen(b); i++)
	{
		int aux;
		if (b[i] >= '0' && b[i] <= '9')aux = b[i] - '0';
		else aux = 10 + b[i] - 'A';
		for(int j=3;j>=0;j--)
		{
			bn[++indx] = (aux & (1 << j));
		}
	}
}
void solve()
{
	long long rez = 0, ap = an, sum = an;
	for (int i = indx; i >= 1; i--)
	{
		if (bn[i])rez = ((rez * ap) % MOD + sum) % MOD;
		sum = (sum * (ap + 1)) % MOD;
		ap = (ap * ap) % MOD;
	}
	g << rez;
}
int main()
{
	citire();
	solve();
	return 0;
}