#include <algorithm>
#include <stdio.h>
#include <map>

#define ll long long
#define MAX 200010

using namespace std;

ll c, restC;
char buffInA[MAX], buffInB[MAX];
int nr[MAX];
map <char, int> mapC;
ll matX[2][2], matRest[2][2];

inline void inmulteste(ll matProd[2][2], ll matFact[2][2])
{
	ll matTemp[2][2];
	memset(matTemp, 0, sizeof(matTemp));

	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				matTemp[i][j] = (matTemp[i][j] + matProd[i][k] * matFact[k][j]) % restC;
	memcpy(matProd, matTemp, sizeof(matTemp));
}

int main()
{
	freopen("calcul.in", "r", stdin);
	freopen("calcul.out", "w", stdout);

	for (char ch = '0'; ch <= '9'; ch++)
		mapC[ch] = ch - '0';
	for (char ch = 'A'; ch <= 'F'; ch++)
		mapC[ch] = ch - 'A' + 10;

	fgets(buffInA, MAX, stdin);
	fgets(buffInB, MAX, stdin);

	scanf("%lld", &c);
	
	restC = 1;
	for (int i = 1; i <= c; i++)
		restC *= 10;

	ll aI = 0;
	for (int i = max((ll) 0, strlen(buffInA) - c - 1); i < strlen(buffInA) - 1; i++)
		aI = aI * 10 + buffInA[i] - '0';
	matX[0][0] = matX[0][1] = aI;
	matX[1][1] = 1;
	matRest[0][0] = matRest[1][1] = 1;

	for (int i = strlen(buffInB) - 2; i >= 0; i--)
	{
		int x = mapC[buffInB[i]];
		for (int i = 0; i < 4; x >>= 1, i++)
			nr[++nr[0]] = x & 1;
	}
	for (; !nr[nr[0]]; nr[0]--);

	for (int i = 1; i < nr[0]; i++)
	{
		if (nr[i])
			inmulteste(matRest, matX);
		inmulteste(matX, matX);
	}

	inmulteste(matX, matRest);

	if (nr[0] > 2)
		for (; matX[0][1] * 10 < restC; restC /= 10)
			printf("0");

	if (matX[0][1])
		printf("%lld\n", matX[0][1]);

	fclose(stdin);
	fclose(stdout);
	return 0;
}