#include <bits/stdc++.h>
///50P
using namespace std;

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

string A, B;

long long c, a, phi;

long long MOD = 1, ans = 1, power;

long long pow_lg(long long base, long long ex)
{
    if(a < 0)
        a += MOD;

    long long pas = 1, p = 1;

    while(ex != 0)
    {
        if(pas & ex)
            ex -= pas, p *= base, p %= MOD;

        base *= base;
        base %= MOD;
        pas *= 2;
    }

    return p;
}

int main()
{
    fin >> A >> B >> c;

    for(int i = 1; i <= c; i++)
        MOD *= 10;

    phi = MOD / 10 * 4;

    for(int i = max((long long)A.size() - c, 0LL); i < A.size(); i++)
        a = a * 10 + (A[i] - '0');

    int T = 1;

    power = a;

    for(int i = B.size() - 1; i >= 0; i--)
    {
        c = B[i];

        if(T == 1)
            c++, T--;

        if(c == char('9' + 1))
            c = 'A';
        if(c == char('F' + 1))
            c = '0', T++;

        int val;

        if(c >= '0' && c <= '9')
            val = c - '0';
        if(c >= 'A' && c <= 'F')
            val = 9 + c - 'A' + 1;

        while(val)
        {
            val--;
            ans *= power;
            ans %= MOD;
        }

        for(int j = 1; j <= 15; j++)
            power *= a, power %= MOD;
    }

    if(T == 1)
    {
        ans *= power;
        ans %= MOD;
    }

    ans -= a;

    if(ans < 0)
        ans += MOD;

    ans *= pow_lg(a - 1, phi - 1);
    ans %= MOD;

    MOD /= 10;

    while(MOD > ans && MOD != 1)
        fout << 0, MOD /= 10;

    fout << ans;

    return 0;
}