#include <stdio.h>
#include <string.h>

const char iname[] = "calcul.in";
const char oname[] = "calcul.out";

#define MAXL  100007

typedef unsigned long long u64;

const u64 Modulo[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

char A_str[MAXL], B[MAXL];


int main(void)
{
	u64 A, Ai, S;
	int C;
	int len;
	int num;
	int meet_one;

	FILE *fi = fopen(iname, "r");
	
	fscanf(fi, "%s\n", A_str);
	fscanf(fi, "%s\n", B);
	fscanf(fi, "%d", &C);
	fclose(fi);

	len = (int)strlen(A_str);
	A = 0;
	for (int i = len >= C ? len - C : 0; i < len; ++ i)
		A = A * 10 + (A_str[i] - '0');
	Ai = A;

	len = (int)strlen(B);
	S = 1;
	meet_one = false;
	for (int k = 0; k < len; ++ k) {
		if ('0' <= B[k] && B[k] <= '9')
			num = B[k] - '0';
		else
			num = B[k] - 'A' + 10;

		for (int i = 1 << 3; i; i >>= 1) {
			if (meet_one) {
				S = ((A + 1) * S) % Modulo[C];
				if (num & i)
					S = (Ai * (S + 1)) % Modulo[C];
				A = (A * A) % Modulo[C];
				if (num & i)
					A = (A * Ai) % Modulo[C];
			} else if (num & i) {
				meet_one = true;
				S = Ai;
			}
		}
	}
	
	FILE *fo = fopen(oname, "w");

	int n_digits = 0;
	for (u64 temp = S; temp; temp /= 10)
		n_digits ++;
	for (; n_digits < C; ++ n_digits)
		fprintf(fo, "0");
	fprintf(fo, "%u", (unsigned long)S);
	fclose(fo);

	return 0;
}