#include <cstring>
#include <fstream>
#include <iostream>

using namespace std;
ifstream f("calcul.in");
ofstream g("calcul.out");
char a[100002], b[50002], cifre[11];
int A, C, MOD;
int main()
{
    f.getline(a, 100002);
    int lgA = f.gcount() - 1;

    f.getline(b, 50002);
    int lgb = f.gcount() - 1, lgB = 0;

    f >> C;
    for(int i = lgA - 1, pt = 1; i >= lgA - C && i >= 0; i--, pt *= 10)
        A = A + (a[i] - 48) * pt;

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

    long long S = 0, P = 1;
    int cif;
    bool bit;
    for(int i = 0; i < lgb; i++)
    {
        if(b[i] >= 'A')
            cif = b[i] + 10 - 'A';
        else cif = b[i] - '0';
        for(int j = 3; j >= 0; j--)
        {
            bit = (cif >> j) & 1;
            S = S * (P + 1) % MOD;
            P = P * P % MOD;
            if(bit)
            {
                P = P * A % MOD;
                S = (S + P) % MOD;
            }
        }
    }

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

    return 0;
}