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

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

string A, B;

long long c, a, phi;

long long MOD = 1, ans, power;

bool bits[200005];
int ct = 0;

long long powers[200005], Spowers[200005];

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

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

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

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

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

        for(int j = 3; j >= 0; j--)
            bits[++ct] = ((val>>j) & 1);
    }

    powers[1] = a;
    Spowers[1] = a;

    for(int i = 2; i <= ct; i++)
    {
        powers[i] = powers[i - 1] * powers[i - 1] % MOD;
        Spowers[i] = Spowers[i - 1] * (powers[i - 1] + 1) % MOD;
    }

    reverse(powers + 1, powers + ct + 1);
    reverse(Spowers + 1, Spowers + ct + 1);

    long long coef = 0;

    for(int i = 1; i <= ct; i++)
        if(bits[i])
        {
            coef++;
            coef %= MOD;

            if(coef == 0)
                coef = (MOD - 1) * powers[i];
            else
                coef = (coef - 1) * powers[i];

            coef %= MOD;

            coef += Spowers[i];

            coef %= MOD;
        }

    MOD /= 10;

    while(MOD != 0 && MOD > coef)
    {
        MOD /= 10;
        fout << 0;
    }
    fout << coef;

    return 0;
}