#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("calcul.in");
ofstream g("calcul.out");
char A[100002], B[50001], Biti[200001], R[10];
int C, Mod, a, b;
int main()
{
    int i,j,n,p,P,S,nrbiti,cifra;
    f >> A >> B >> C;
    Mod = 1;
    for(i = 1; i <= C; i++) Mod *= 10;

    n = strlen(A);
    for(i = n - 1, p = 1; i >= n - 1 - C && i >= 0; i--, p *= 10)
        a = (A[i] - '0') * p + a;
    nrbiti = 0;
    for(i = 0; B[i] != 0; i++)
    {
        if(B[i] >= 'A') cifra = B[i] - 'A' + 10;
        else cifra = B[i] - '0';
        for(j = 3; j >= 0; j--)
            Biti[++nrbiti] = ((cifra >> j) & 1);
    }
    P = 1;
    S = 0;
    for(i = 1; i <= nrbiti; i++)
    {
        S = 1LL * S * (1 + P) % Mod;
        P = 1LL * P * P % Mod;
        if(Biti[i] > 0)
        {
            P = (1LL * P * a) % Mod;
            S = (S + P) % Mod;
        }
    }

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