#include <cstdio>
#include <fstream>

#define MAXA 100001
#define MAXB 50001
#define ll long long

char a[MAXA], b[MAXB], B[MAXB * 4];

int c, C;
ll A, put, sol;

char frm[8] = "%00lld\n";

int main()
{
	freopen("calcul.in", "rt", stdin);
	freopen("calcul.out", "wt", stdout);
	
	gets(a);
	gets(b);
	
	scanf("%d", &c); frm[2] = c + '0';
	int i, j;
	
	for (i = 0; a[i + 1]; i++);
	
	for (A = j = 0, C = 1; i + 1 && j < c; i--, j++, C *= 10)
		A += C * (a[i] - '0');
	for (; j < c; j++) C *= 10;

	for (i = j = 0; b[i]; i++)
	{
		b[i]=('A' <= b[i] && b[i] <= 'Z') ? b[i] - ( 'A' - 10 ) : b[i] - '0';
		B[j++] = b[i] >> 3;
		B[j++] = (b[i] >> 2) & 1;
		B[j++] = (b[i] >> 1) & 1;
		B[j++] = b[i] & 1;
	}

	for (sol = 0, put = 1, i = 0; i < j; i++)
	{
		sol = (sol * ((1 + put) % C)) % C;
		put = (put * put) % C;
		if (B[i] == 1)
			sol = (A * ((1 + sol) % C)) % C,
			put = (put * A) % C;
	}
	
	printf(frm, sol);
	return 0;
}