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

#define MAX_N 100010

char s[MAX_N];
int A, c, mod, nr, start = 1;
int sol[2][2], init[2][2];
                              
void cit() {
	freopen("calcul.in", "r", stdin);
	freopen("calcul.out", "w", stdout);

	//citesc A si pastrez ultimele 9 cifre
	scanf("%s", s);
	int len = strlen(s) - 1, down = len - 8;
	if (down < 0) down = 0;
	for (int i = down; i <= len; i++)
		A = A * 10 + s[i] - 48;

	scanf("%s", s);
	scanf("%d", &c);

	mod = 1;
	while (c--) mod *= 10;
}

void inm(int P[2][2], int Q[2][2]) {
	int mat[2][2];

	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++) {
			mat[i][j] = 0;
			for (int k = 0; k < 2; k++)
				mat[i][j] = ((long long) mat[i][j] + 1LL * P[i][k] * Q[k][j]) % mod;
		}

	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			P[i][j] = mat[i][j];
}

void cop(int P[2][2], int Q[2][2]) {
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			P[i][j] = Q[i][j];
}

void solve() {
	init[0][0] = A; init[0][1] = init[1][1] = 1;
	cop(sol, init);

	int len = strlen(s) - 1;
	for (int i = 0; i <= len; i++) {
		if ('A' <= s[i] && s[i] <= 'F') nr = s[i] - 'A' + 10;
		else nr = s[i] - '0';

		for (int k = 3; k >= 0; k--)
			if (nr & (1 << k))
				if (start) {
                	cop(sol, init);
					start = 0;
				}
				else {
					inm(sol, sol);
					inm(sol, init);
				}
			else inm(sol, sol);
	}

	int val = ((long long) sol[0][0] + sol[0][1] - 1) % mod;
	if (val < 0) val += mod;

	printf("%d\n", val);
}

int main() {

	cit();
	solve();

	return 0;
}