#include <bits/stdc++.h>

using namespace std;

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

string A, B;
int C, mod = 1, N, a, mask, x = 1, ans;
vector<bool> bits;

void add_self(int &a, int b) {
    a += b;
    if(a >= mod)
        a -= mod;
}

int main(){
    fin >> A >> B >> C;
    for(int i = 0; i < C; ++i)
        mod *= 10;
    N = A.size();
    for(int i = max(N - C, 0); i < N; ++i)
        a = a * 10 + (A[i] - '0');
    N = B.size();
    for(int i = 0; i < N; ++i) {
        mask = (B[i] >= 'A') ? B[i] - 'A' + 10 : B[i] - '0';
        for(int j = 3; j >= 0; --j)
            bits.emplace_back((mask >> j) & 1);
    }
    for(const auto &bit : bits) {
        ans = 1LL * ans * (x + 1) % mod;
        x = 1LL * x * x % mod;
        if(bit) {
            x = 1LL * x * a % mod;
            add_self(ans, x);
        }
    }
    mod /= 10;
    while(ans < mod)
        fout << '0', mod /= 10;
    if(mod)
        fout << ans;
    fout << '\n';
}