#include<bits/stdc++.h>

using namespace std;
ifstream f("calcul.in");
ofstream g("calcul.out");

char A[100005], B[1250], Bit[5000];
int  C, MOD, NrBit, S;

int main()
{
    int i, lgA, lgB, a, cif, P;
    f.getline(A, 100002);
    lgA = f.gcount() - 1;
    f.getline(B, 1250);
    lgB = f.gcount() - 1;
    f >> C;
//
    MOD = 1;
    for(i = 1; i <= C; i++)
        MOD *= 10;
//
    a = 0;
    for(i = max(lgA - C, 0); i < lgA; i++)
        a = a * 10 + A[i] - '0';
//
    NrBit = 0;
    for(i = 0; i < lgB; i++)
    {
        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;
    }
//
    P = 1;
    S = 0;
    for(i = 1; i <= NrBit; i++)
    {
        S = 1LL * S * (1 + P) % MOD;
        P = 1LL * P * P % MOD;
        if(Bit[i] > 0)
        {
            P = 1LL * P * a % MOD;
            S = (S + P) % MOD;
        }
    }
//
    MOD /= 10;
    for(; S < MOD; MOD /= 10)
        g << '0';
    if(MOD) g << S;
    return 0;
}