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

const int N 200010

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

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