#include <cstdio>
#include <cstring>

using namespace std;

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

inline void scade(char s[]) {
	int i = 0;
	while (s[i] == 0) {
		s[i] = 9;
		i++;
	}
	s[i]--;
	for (; n > 1 && !s[n]; n--);	
}

inline void divide(char A[]) {
	int i, t = 0;
    for (i = n; i >= 0; i--, t %= 2)
        A[i] = (t = t * 10 + A[i]) / 2;
    for (; n > 0 && !A[n]; n--);
}

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 p[3][3];
	if (n == 0 && b[0] == 1) {
		memcpy(m, mat, sizeof(mat));
		return;
	}
	
	if (b[0] % 2 == 0) {
		divide(b);
		memset(p, 0, sizeof(p));
		lg_pow(p);
		mult(p, p, m);
	}
	else {
		scade(b);
		memset(p, 0, sizeof(p));
		lg_pow(p);
		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')
			b[i] = b[i] - 'A' + 10;
		else
			b[i] -= 48;
	}
	
	mat[1][1] = a; mat[1][2] = 1; mat[2][1] = 0; mat[2][2] = 1;
	scade(b);
	lg_pow(t1);
	
	t2[1][1] = a * a; t2[1][2] = a; t2[2][1]  = a; t2[2][2] = 0;
	mult(t2, t1, sol);
	
	printf("%d\n", sol[1][2]);
	
	return 0;
}