#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

const int S = 2, MAXA = 100010, MAXB = 50010;
char input[MAXA], hex1[MAXB], hexVal[16][5];
int a, c, mod = 1;

ifstream fin("calcul.in");
ofstream fout("calcul.out");

int hexToDec(char c) {
    if (c == 'A')
        return 10;
    if (c == 'B')
        return 11;
    if (c == 'C')
        return 12;
    if (c == 'D')
        return 13;
    if (c == 'E')
        return 14;
    if (c == 'F')
        return 15;
    return c - '0';
}

int digitNumber(int x) {
    int nr = 0;
    do {
        ++nr;
        x /= 10;
    } while(x);
    return nr;
}

struct Matrix{
    int mat[S][S], n, m;
    Matrix() {
        n = 0;
        m = 0;
        for (int i = 0; i < S; ++i)
            for (int j = 0; j < S; ++j)
                mat[i][j] = 0;
    }
    Matrix &operator=(const Matrix &other) {
        n = other.n;
        m = other.m;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                mat[i][j] = other.mat[i][j];
        return (*this);
    }
    Matrix operator*(const Matrix &other) {
        Matrix result;
        result.n = n;
        result.m = other.m;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < other.m; ++j)
                for (int k = 0; k < m; ++k)
                    result.mat[i][j] = (result.mat[i][j] + (1ll * mat[i][k] * other.mat[k][j]) % mod) % mod;
        return result;
    }
    Matrix solve() {
        Matrix res, mult;
        mult = (*this);
        res.n = 2;
        res.m = 2;
        res.mat[0][0] = 1;
        res.mat[1][1] = 1;
        for (int i = strlen(hex1) - 1; i >= 0; --i) {
            int nr = hexToDec(hex1[i]);
            for (int i = 0; i < 4; ++i) {
                if (hexVal[nr][i] == '1')
                    res = res * mult;
                mult = mult * mult;
            }
        }
        return res;
    }
};

void initialize() {
    strcpy(hexVal[0], "0000");
    strcpy(hexVal[1], "1000");
    strcpy(hexVal[2], "0100");
    strcpy(hexVal[3], "1100");
    strcpy(hexVal[4], "0010");
    strcpy(hexVal[5], "1010");
    strcpy(hexVal[6], "0110");
    strcpy(hexVal[7], "1110");
    strcpy(hexVal[8], "0001");
    strcpy(hexVal[9], "1001");
    strcpy(hexVal[10], "0101");
    strcpy(hexVal[11], "1101");
    strcpy(hexVal[12], "0011");
    strcpy(hexVal[13], "1011");
    strcpy(hexVal[14], "0111");
    strcpy(hexVal[15], "1111");
}

void read() {
    fin.getline(input, MAXA);
    fin.getline(hex1, MAXB);
    fin >> c;
    int s =  strlen(input);
    for (int i = s - c; i < s; ++i) {
        if (i >= 0)
            a  = a * 10 + (input[i] - '0');
        mod *= 10;
    }
}

void print(int x) {
    int nr = digitNumber(x);
    for (int i = 0; i < c - nr; ++i)
        fout << '0';
    fout << x << '\n';
}

int main() {
    Matrix result;
    initialize();
    read();
    result.n = 2;
    result.m = 2;
    result.mat[0][0] = 1;
    result.mat[0][1] = 0;
    result.mat[1][0] = a;
    result.mat[1][1] = a;
    result = result.solve();
    print(result.mat[1][0]);
    return 0;
}