#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

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

const int NMAX = 20010;

char s[NMAX], b[NMAX];
int bit[NMAX];
int c, n, mask, bits = 0;
long long MOD = 1, a = 0, x = 1, ans = 0;

int main(){
    in >> s >> b >> c;
    for(int i = 1; i <= c; i++)
        MOD*=10;
    n = strlen(s);
    for(int i = 0; i < n; i++)
        a = ( a * 10 + s[i] - '0') % MOD;
    n = strlen(b);
    for(int i = 0; i < n; i++){
        if(b[i] >= 'A')
            mask = b[i] - 'A' + 10;
        else
            mask = b[i] - '0';
        for(int j = 3; j >= 0; j--){
            bits++;
            bit[bits] = ((mask>>j) & 1);
        }
    }
    for(int i = 1; i <= bits; i++){
        ans = ( ans * (x+1)) % MOD;
        x = (x * x) % MOD;
        if(bit[i] > 0){
            x = (x * a) % MOD;
            ans = (ans + x) % MOD;
        }
    }
    for(int i = 1; i < c; i++){
        MOD /= 10;
        if(ans < MOD)
          out << 0;
    }
    out << ans;
    return 0;
}