#include <bits/stdc++.h>
//#include "functions.hpp"
using namespace std;
#define ll long long

// Modular exponentiation: (base^exp) % mod
ll mod_exp(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

// Convert a hexadecimal string to a decimal number modulo a given mod
ll hex_to_dec_mod(const string &hex, ll mod) {
    ll result = 0;
    for (char ch: hex) {
        result = (result * 16 + (isdigit(ch) ? ch - '0' : ch - 'a' + 10)) % mod;
    }
    return result;
}

int main() {
    string A_str, B_str;
    int C;
    ifstream fin("calcul.in");
    ofstream fout("calcul.out");
    fin >> A_str >> B_str >> C;
    fin.close();

    ll MOD = 1;
    for (int i = 0; i < C; ++i) MOD *= 10; // MOD = 10^C

    // Reduce A modulo MOD
    ll A = 0;
    for (char ch: A_str) {
        A = (A * 10 + (ch - '0')) % MOD;
    }

    if (A == 0) {
        fout << setw(C) << setfill('0') << 0 << endl;
        fout.close();
        return 0;
    }

    // Convert B (hexadecimal) to decimal modulo cycle length
    ll B_mod = hex_to_dec_mod(B_str, MOD);

    // Find cycle in A^n % MOD
    unordered_map<ll, ll> seen;
    vector<ll> sequence;
    ll current = A;
    while (seen.find(current) == seen.end()) {
        seen[current] = sequence.size();
        sequence.push_back(current);
        current = (current * A) % MOD;

        if (sequence.size() > MOD) break;
    }

    ll cycle_start = seen[current];
    ll cycle_length = sequence.size() - cycle_start;

    // Compute the sum A^1 + A^2 + ... + A^B % MOD
    ll sum = 0;

    if (B_mod <= cycle_start) {
        for (ll i = 0; i < B_mod; ++i) {
            sum = (sum + sequence[i]) % MOD;
        }
    } else {
        // Sum pre-cycle
        for (ll i = 0; i < cycle_start; ++i) {
            sum = (sum + sequence[i]) % MOD;
        }

        // Sum complete cycles
        ll cycle_sum = 0;
        for (ll i = cycle_start; i < sequence.size(); ++i) {
            cycle_sum = (cycle_sum + sequence[i]) % MOD;
        }
        ll full_cycles = (B_mod - cycle_start) / cycle_length;
        sum = (sum + full_cycles * cycle_sum) % MOD;

        // Sum remaining terms in the last partial cycle
        ll remaining = (B_mod - cycle_start) % cycle_length;
        for (ll i = 0; i < remaining; ++i) {
            sum = (sum + sequence[cycle_start + i]) % MOD;
        }
    }

    fout << setw(C) << setfill('0') << sum << endl;
    fout.close();
    return 0;
}