/* [A][M][C][B][N] / [K][R][I][P][6][8] */
// In the name of God
#include <bits/stdc++.h>
using namespace std;
const int mod = 104659, inf = 0x3f3f3f3f;
const char sp = ' ', nl = '\n';
ifstream fin("calcul.in");
ofstream fout("calcul.out");
long long x = 0, ans = 1;
string a, b;
int c;
long long M = 1;

long long mypow(long long n, long long p) {
    if (!p) return 1;
    long long rt = mypow(n, p >> 1);
    return ((rt * rt) % M) * (p & 1 ? n : 1) % M;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // (A^(n + 1) - A^1) / (A - 1)
    fin >> a >> b >> c;
    for (int i = max((int)a.size() - c, 0); i < a.size(); ++i)
        x = x * 10 + a[i] - '0';
    for (int i = 1; i <= c; ++i)
        M *= 10;
    for (int i = 0; i < b.size(); ++i) {
        for (int j = 0; j < 4; ++j) {
            int val = b[i] <= '9' ? b[i] - '0' : b[i] - 'A' + 10;
            ans = (ans * ans) % M;
            if ((val >> (3 - j)) & 1) {
                ans = (ans * x) % M;
            }
        }
    }
    ans = ((ans * x) % M - x + M) % M;
    ans = (ans * mypow(x - 1, M / 10 * 4 - 1)) % M;
    fout << string(c - to_string(ans).size(), '0') + to_string(ans);
}