#include <fstream>
#include <iomanip>
 
#define MAX 200005
 
using namespace std;
 
string sA, sB;
int A, C, MOD;
int B[MAX], nrBit;
long long ans;
 
void citire() {
    ifstream in("calcul.in");
    in>>sA>>sB>>C;
    in.close();
}
 
void solve() {
    /* getting 10^C */
    int MOD = 1;
    for(int i = 1; i <= C; i++) MOD *= 10;
    /* getting A */
    for(size_t i = 0; i < sA.size(); i++) A = (1LL * A * 10 + sA[i] - '0') % MOD;
    /* getting binary representation of B */
    for(int i = sB.size() - 1, digit; i >= 0; i--) {
        if(isdigit(sB[i])) digit = sB[i] - '0';
        else digit = 10 + sB[i] - 'A';
        for(int bit = 0; bit < 4; bit++) {
            B[++nrBit] = digit & 1;
            digit >>= 1;
        }
    }
    /* removing starting zeroes */
    for(; !B[nrBit]; nrBit--);
    /* getting the last C digits of sum(A^k) */
    ans = A; // last C digits of A^1
    long long put = A; // the power of the last member in the sequence considered
    for(int i = nrBit - 1; i; i--) {
        ans += ans * put;
        put *= put;
        if(ans >= MOD) ans %= MOD;
        if(put >= MOD) put %= MOD;
        if(B[i]) {
            ans += (put *= A);
            if(ans >= MOD) ans %= MOD;
            if(put >= MOD) put %= MOD;
        }
    }   
}
 
void afisare() {
    ofstream out("calcul.out");
    out << setfill('0') << setw(C) << ans <<"\n";
    out.close();
}
 
int main() {
    citire();
    solve();
    afisare();
}