#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 100050

using namespace std;

char a[MAXN], b[MAXN];
int c, mod, A;

void citire()
{
	gets(a);
	gets(b);
    scanf("\n%d", &c);
    mod = 10;
    for (int i = 1; i < c; i++)
		mod *= 10;
	int st = std::max(0, (int)strlen(a)-c);
    for (int i = st; i < strlen(a); i++)
        A = A*10 + a[i]-'0';
}

int getBit(int ind) /// al ind-lea bit a lui b de la coada
{
    char x = b[strlen(b)-1-(ind/4)];
    int bit = (ind%4);
    if (x >= '0' && x <= '9')
        return ((x-'0') & (1<<bit));
    else
		return ((x-'A'+10) & (1<<bit));
}

void mult(int x[2][2], int y[2][2])
{
    int rez[2][2] = {{0, 0}, {0, 0}};
    for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				rez[i][j] = (rez[i][j] + 1LL*x[i][k]*y[k][j])%mod;
    for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			x[i][j] = rez[i][j];
}

void rise(int m[2][2])
{
    int rez[2][2] = {{1, 0}, {0, 1}};
    for (int i = 0, t = 4*strlen(b); i < t; i++) {
        if (getBit(i))
			mult(rez, m);
		mult(m, m);
    }
    for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			m[i][j] = rez[i][j];
}

void solve()
{
//    printf("%d\n", A);
//    for (int i = 0; i < 4*strlen(b); i++)
//		printf("%d", getBit(i));
//    printf("\n%d", mod);
    int matrix[2][2] = {{A, 0}, {A, 1}};
    rise(matrix);
    printf("%d", matrix[1][0]);
}

int main()
{
    freopen("calcul.in", "r", stdin);
    freopen("calcul.out", "w", stdout);

    citire();
    solve();

    return 0;
}