#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("calcul.in");
ofstream g("calcul.out");
char A[100002], B[500002], Bit[200010], R[20];
int C, MOD=1, NrBit, S,P;

int main()
{
    f.getline(A, 100002);
    f.getline(B, 500002);
    f >> C;
    //
    int lgA = strlen(A);
    int lgB = strlen(B);
    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;
    }
    P = 1;
    S = 0;
    for(int 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;
        }
    }
    for(int i = C - 1; i >= 0; i--)
    {
        R[i] = S % 10 + '0';
        S /= 10;
    }
    g << R;
    return 0;
}