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

#define MAX_N 100010
#define ll long long

char s[MAX_N];
int A, c, mod, nr, start = 1;
ll sol[2][2], init[2][2], val;
                              
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(ll P[2][2], ll Q[2][2]) {
	ll 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] = (mat[i][j] + 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(ll P[2][2], ll 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;

	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);
	}

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

	ll cop = val; if (!cop) cop = 1;
	while (cop * 10 < mod) {
    	cop *= 10;
		printf("0");
	}

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

int main() {

	cit();
	solve();

	return 0;
}