#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

ifstream fin ("calcul.in");
ofstream fout ("calcul.out");

char aorig[100001], borig[50001];
int conv[128];

bool b[200001];
int p2a[200001];

int dp[200001], voll[200001];

int main()
{
	int i, c, a, lga, lgb, j, r;
	fin >> aorig >> borig >> c;
	lga = strlen (aorig);
	lgb = strlen (borig);
	
	r = 1;
	for (i = 1; i<=c; i++)
		r = 10 * r;
	
	a = 0;
	for (i = max(0, lga - c); i < lga; i++)
		a = 10 * a + aorig[i] - '0';
	
	for (i = 0; i<=9; i++)
		conv[i + '0'] = i;
	for (i = 'A'; i<='F'; i++)
		conv[i] = i - 'A' + 10;
	
	for (i = lgb - 1; i>=0; i--)
		for (j = 0; j<4; j++)
			if (conv[borig[i]] & (1<<j))
				b[4*(lgb - i - 1) + j] = 1;
	
	p2a[0] = a;
	for (i = 1; i<=4 * lgb; i++)
		p2a[i] = 1ll * p2a[i-1] * p2a[i-1] % r;
	
	voll[0] = (a + 1) % r;
	if (b[0] == 1)
		dp[0] = voll[0];
	else
		dp[0] = 1;
	
	for (i = 1; i<4*lgb; i++)
	{
		if (b[i] == 0)
			dp[i] = dp[i-1];
		else
			dp[i] = (voll[i-1] + 1ll * dp[i-1] * p2a[i]) % r;
		
		voll[i] = (voll[i-1] + 1ll * p2a[i] * voll[i-1]) % r;
	}
	
	int rasp = (dp[4*lgb-1] - 1 + r) % r;
	char afis[10] = {};
	j = 0;
	while (rasp)
	{
		afis[c-j-1] = rasp % 10 + '0';
		rasp = rasp / 10;
		j++;
	}
	for (; j<c; j++)
		afis[c-j-1] = '0';
	fout << afis;
	return 0;
}