#include <cstdio>
#include <cassert>

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int Mod, Base, Solution;
string Power;

int ComputeSum(const int base, const string &power) {
    int result = base;
    for (int i = 1, basePow = base; i < static_cast<int>(power.length()); ++i) {
        result = (result + 1LL * basePow * result) % Mod;
        basePow = (1LL * basePow * basePow) % Mod;
        if (power[i] == '1') {
            basePow = (1LL * basePow * base) % Mod;
            result = (result + 1LL * basePow) % Mod;
        }
    }
    return result;
}

void Solve() {
    Solution = ComputeSum(Base, Power);
}

void Read() {
    assert(freopen("calcul.in", "r", stdin));
    string stringBase, base16Power;
    int modPower;
    cin >> stringBase >> base16Power >> modPower;
    for (Mod = 1; modPower > 0; --modPower)
        Mod *= 10;
    for (int i = 0; i < static_cast<int>(stringBase.length()); ++i)
        Base = (10 * Base + (stringBase[i] - '0')) % Mod;
    for (int i = static_cast<int>(base16Power.length()) - 1; i >= 0; --i) {
        int digit;
        if ('0' <= base16Power[i] && base16Power[i] <= '9')
            digit = base16Power[i] - '0';
        else
            digit = 10 + base16Power[i] - 'A';
        for (int bit = 0; bit < 4; ++bit)
            Power.push_back('0' + ((digit >> bit) & 1));
    }
    for (; !Power.empty() && Power.back() == '0'; Power.pop_back());
    reverse(Power.begin(), Power.end());
}

void Print() {
    assert(freopen("calcul.out", "w", stdout));
    printf("%d\n", Solution);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}