#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;
}