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

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

const int N = 200010;

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

int main() {
    int i,j;

    in >> 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)
            out << 0;
    }
    out << sol << "\n";

    return 0;
}