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

using namespace std;

char a[MAXN], b[MAXN];
bitset <4*MAXN> bits;
int c, mod, A, nq;

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';
	for (int i = strlen(b)-1; i >= 0; i--) {
		int nr = (b[i] >= '0' && b[i] <= '9') ? b[i]-'0' : b[i]-'A'+10;
		for (int j = 0; j < 4; j++)
            bits[nq++] = ((nr>>j) & 1);
	}
}

//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] = (0LL + 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 (bits[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);
    int rez = matrix[1][0];
    for (int i = 1; i < c; i++)
    {
        mod /= 10;
        if (rez < mod)
			printf("0");
    }

    printf("%d", matrix[1][0]);
}

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

    citire();
    solve();

    return 0;
}