#include <bits/stdc++.h>

using namespace std;

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

char A[100002], B[50002], bit[200002], R[20];
int C, MOD, nrBit, S, P;


int main()
{
    in.getline(A, 100002);
    int lgA = in.gcount() - 1;

    in.getline(B, 50002);
    int lgB = f.gcount() - 1;

    in >> C;

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

    int a = 0;
    for(int i = max(lgA - C), 0); i < lgA; i++)
        a = a * 10 + A[i] - '0';

    for(int i = 0; i < lgB; i++) {
        int cif;
        if(B[i] >= 'A')
            cif = B[i] - 'A' + 10;
        else cif = B[i] - '0';

        for(int j = 3; j >= 0; j--)
            bit[++nrBit] = (cif >> j) & 1;
    }

    int P = 1, S = 0;

    for(int i = 1; i <= nrBit; i++) {
        S = 1LL * S * (P+1) % MOD;
        P = 1LL * P * P % MOD;
        if(bit[i] > 0) {
            P = 1LL * P * a % MOD;
            S = (S+P) % MOD;
        }
    }

    for(int i = C-1; i >= 0; i--) {
        R[i] = S % 10 + '0';
        S /= 10;
    }

    out << R << '\n';
    return 0;
}