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

#define MAX_N 100010

char s[MAX_N];
int A, c, mod;
int sol[2][2], prec[16][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() {
    prec[0][0][0] = A; prec[0][0][1] = prec[0][1][1] = 1;
	for (int i = 1; i <= 15; i++) {
		cop(prec[i], prec[i - 1]);
		inm(prec[i], prec[0]);	
	}

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

		if (nr - 1 >= 0) {
			if (i) inm(sol, prec[nr - 1]);
			else cop(sol, prec[nr - 1]);
		}
	}

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