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