#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

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

const int nmax = 200010;

int n, m, i, c, j, pt, bt[nmax];
long long sol, a, mod, ac;
char s[nmax], b[nmax];

int main()
{
    int i,j;
    fin >> s >> b >> c;
    pt=c;
    mod=1;
    for(i=1; i<=c; ++i)
        mod *= 10;

    n=strlen(s);
    for(i=0; i!=n; ++i)
        a=((long long)a*10 + s[i] - '0')%mod;

    n=strlen(b);
    for(i=0; i!=n; ++i)
    {
        if(b[i] >= 'A') c = 10 + b[i] - 'A';
        else c = b[i] - '0';
        for(j = 3; j>=0; --j)
            bt[++m] = ((c>>j)&1);
    }
    ac=1;
    for(i=1; i<=m; ++i)
    {
        sol = sol*(1 + ac)%mod;
        ac=((long long)ac * ac)%mod;
        if(bt[i])
        {
            ac = (ac * a)%mod;
            sol = (sol + ac)%mod;
        }
    }

    for(i=1; i<pt; ++i)
    {
        mod/=10;
        if(sol<mod) fout << 0;
    }
    fout << sol << "\n";
    fin.close();
    fout.close();
    return 0;
}