#include<fstream>
#include<cstring>
using namespace std;
int c, m, i, sum, val, x, j, aux, p, mod;
char s[100005];
int v[200005];
ifstream fin("calcul.in");
ofstream fout("calcul.out");
int main(){
    fin>> s + 1;
    m = strlen(s + 1);
    for(i = max(1, m - 9 + 1); i <= m; i++){
        x = x * 10 + s[i] - '0';
    }
    fin>> s + 1;
    m = strlen(s + 1);
    fin>> c;
    for(i = m; i >= 1; i--){
        if(s[i] >= '0' && s[i] <= '9'){
            aux = s[i] - '0';
        }
        else{
            aux = 10 + s[i] - 'A';
        }
        for(j = 0; j < 4; j++){
            v[++p] = aux % 2;
            aux /= 2;
        }
    }
    while(v[p] == 0){
        p--;
    }
    mod = 1;
    for(i = 1; i <= c; i++){
        mod *= 10;
    }
    x %= mod;
    sum = val = x;
    for(i = p - 1; i >= 1; i--){
        if(v[i] == 0){
            sum = sum * 1LL * (1 + val) % mod;
            val = val * 1LL * val % mod;
        }
        else{
            sum = (sum + val * 1LL * x % mod * (1 + sum) ) % mod;
            val = val * 1LL * val % mod * x % mod;
        }
    }
    mod /= 10;
    while(mod > 1 && sum < mod){
        fout<< 0;
        mod /= 10;
    }
    fout<< sum <<"\n";
    return 0;
}