#include<fstream>
#include<cstring>
using namespace std;
ifstream in ("calcul.in");
ofstream out ("calcul.out");
int biti,c,vaux[5],d,mod;
long long v[200001],a[200001];
int b[2000001];
char auxa[200001], auxb[200001];
int main (void) {
    in >> auxa + 1;
    in >> auxb + 1;
    in >> c;
    int lun = strlen (auxa+1);

    for (int i = strlen(auxb+1); i >= 1; i --) {
        int aux;
        if (auxb[i] >= '0' && auxb[i] <= '9') {
            aux = auxb[i] - '0';
        }
        if (auxb[i] >= 'A' && auxb[i] <= 'F') {
            aux = auxb[i] - 'A' + 10;
        }

        for (int j = 1; j <= 4; j ++) {
            vaux[j] = 0;
        }
        d = 0;
        while (aux > 0) {
            vaux[++d] = aux % 2;
            aux /= 2;
        }

        for (int j = 1; j <= 4; j ++) {
            b[++biti] = vaux[j];
        }
    }
    mod = 1;
    for (int i = 1; i <= c; i ++) {
        mod *= 10;
    }
    int x = 0;
    while (b[biti] == 0) {
        biti --;
    }

    for (int i = max (1,lun-c+1); i <= lun; i ++){
        a[biti] = a[biti] * 10 + auxa[i] - '0';
    }

    for (int i = biti; i >= 1; i --) {
        if (i == biti) {
            continue;
        }
        else {
            a[i] = (1LL * a[i+1] * a[i+1]) % mod;
            if (b[i] == 1) {
                a[i] = (1LL * a[i] * a[biti]) % mod;
            }
        }
    }

    for (int j = biti; j >= 1; j --) {
        if (b[j] == 0) {
            v[j] = (1LL * v[j+1] * (1 + a[j+1])) % mod;
        }
        else {
            v[j] = ((1LL*( 1LL*(v[j+1] * (1 + a[j+1])) % mod ) * a[biti]) % mod + a[biti]) % mod;
        }
    }

    x = v[1];
    int cnt = 0;
    while (x > 0) {
        cnt ++;
        x /= 10;
    }
    while (cnt < c) {
        cnt ++;
        out << 0;
    }
    out<< v[1];
    return 0;
}