#include <bits/stdc++.h>
using namespace std;

int MOD = 1, c;
char s[100005], s2[100005];
int ans[2][2], aux[2][2];

inline void inm(int A[2][2], int B[2][2]){
    int C[2][2];
    memset(C, 0, sizeof(C));
    for(int i = 0; i < 2 ; ++i){
        for(int j = 0; j < 2 ; ++j){
            for(int k = 0; k < 2 ; ++k)
                C[i][j] = (C[i][j] + (1LL * A[i][k] * B[k][j]) % MOD) % MOD;
        }
    }
    memcpy(A, C, sizeof(C));
}

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

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

    for(int i = 1; i <= c ; ++i) MOD *= 10;
    int L = strlen(s2), x = 0;
    for(int i = max(0, L - c); i < L ; ++i) x = x * 10 + s2[i] - '0';

    aux[0][0] = 1; aux[0][1] = 1; aux[1][0] = 0; aux[1][1] = x;
    ans[0][0] = 0; ans[0][1] = 0; ans[1][0] = x; ans[1][1] = 0;

    L = strlen(s);
    for(int i = L - 1; i >= 0 ; --i){
        int M = 0;
        if(s[i] >= 'A') M = M + s[i] - 'A' + 10;
        else M = M + s[i] - '0';

        for(int i = 1; i <= 8 ; i = i << 1){
            if(i & M) inm(ans, aux);
            inm(aux, aux);
        }
    }

    if(ans[1][1] == 0){
        for(int i = 1; i <= c ; ++i)
            printf("0");
        return 0;
    }

    int X = ans[1][1];
    while(1LL * X * 10 < MOD) X = X * 10, printf("0");
    printf("%d", ans[1][1]);

    return 0;
}