#include <stdio.h>

const int MAXA = 100001;
const int MAXB = 50001;
char a[MAXA], b[MAXB], B[MAXB * 4];
int c, C;
long long 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++)
	{
		if ('A' <= b[i] && b[i] <= 'Z')
			b[i] -= 'A' - 10;
		else
			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;
}