#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int nmax = 200010;
long long sol, a, mod=1, x=1;
char s[nmax], b[nmax];
bool bt[nmax];

int main()
{
    ifstream fin("calcul.in");
    ofstream fout("calcul.out");
    int i, j, m=0, c, cc;
    fin >> s >> b >> c;
    cc=c;
    for(i=1; i<=c; i++)
        mod=mod*10;
    for(i=0; i<strlen(s); i++)
        a=((long long)a*10+s[i]-'0')%mod;

    for(i=0; i<strlen(b); 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);
    }

    for(i=1; i<=m; i++)
    {
        sol=sol*(1+x)%mod;
        x=((long long)x*x)%mod;
        if(bt[i])
        {
            x=(x*a)%mod;
            sol=(sol+x)%mod;
        }
    }

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