#include <cstdio>
#include <cstring>

using namespace std;

char s[100100], b[100100];
char t[400100];
int c, a, i, j, n, mod, d, nr;
int mat[3][3], t1[3][3], t2[3][3], sol[3][3];

inline void scade() {
	int i = 1;
	while (t[i] == 0) {
		t[i] = 1;
		i++;
	}
	t[i]--;
	for (; d > 1 && !t[d]; d--);	
}

inline void mult(int a[][3], int b[][3], int c[][3]) {
	int i, j, k;
	for (i = 1; i <= 2; i++)
		for (j = 1; j <= 2; j++)
			for (k = 1; k <= 2; k++)
				c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
}


void lg_pow(int m[][3], int ind) {
	int p[3][3];
	if (ind == d) {
		memcpy(m, mat, sizeof(mat));
		return;
	}
	
	if (t[ind] % 2 == 0) {
		memset(p, 0, sizeof(p));
		lg_pow(p, ind + 1);
		mult(p, p, m);
	}
	else {
		t[ind] = 0;
		memset(p, 0, sizeof(p));
		lg_pow(p, ind);
		mult(p, mat, m);
	}
}

inline void swap(char &a, char &b) {
	char aux;
	aux = a; a = b; b = aux;
}

inline int max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

int main() {
	freopen("calcul.in", "r", stdin);
	freopen("calcul.out", "w", stdout);
	
	scanf(" %s ", s);
	scanf(" %s ", b);
	scanf("%d", &c);
	
	mod = 1; 
	for (i = 1; i <= c; i++)
		mod *= 10;
	
	for (n = 0; s[n] != 0; n++);
	n--;
	
	for (i = max(n - c + 1, 0); i <= n; i++)
		a = a * 10 + (s[i] - 48);
	
	for (n = 0; b[n] != 0; n++);
	n--;
	
	for (i = 0; i <= n / 2; i++)
		swap(b[i], b[n - i]);
	
	for (i = 0; i <= n; i++) {
		if (b[i] >= 'A')
			nr = b[i] - 'A' + 10;
		else
			nr = b[i] - 48;
		
		while (nr > 0) {
			d++;
			t[d] = nr % 2;
			nr /= 2;
		}
		
		if (i < n)
			while (d != 4 * i + 4) {
				d++;
				t[d] = 0;
			}
	}
	
	scade();
	
	mat[1][1] = a; mat[1][2] = 1; mat[2][1] = 0; mat[2][2] = 1;
	if (t[d] != 0) {
		lg_pow(t1, 1);
		t2[1][1] = a * a; t2[1][2] = a; t2[2][1]  = a; t2[2][2] = 0;
		mult(t2, t1, sol);
	}
	else
		sol[1][2] = a;
	
	int aux = sol[1][2];
	while (aux * 10 < mod) {
		aux *= 10;
		printf("0");
	}
	
	printf("%d\n", sol[1][2]);
	
	return 0;
}