#include<fstream>
#include<cstring>
using namespace std;
ifstream in ("calcul.in");
ofstream out ("calcul.out");
int biti,a[200001],c,vaux[5],d,mod;
long long v[2000001];
bool b[2000001];
char auxa[100001], auxb[200001];

int main (void) {
    in >> auxa + 1;
    in >> auxb + 1;
    in >> c;
    int lun = strlen (auxa+1);

    for (int i = 1; i <= strlen(auxb+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' + 11;
        }

        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] = (a[i+1] * a[i+1]) % mod;
            if (b[i] == 1) {
                a[i] = (a[i] * a[biti]) % mod;
            }
        }
    }

    for (int j = biti; j >= x; 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;
        }
    }
    out << v[1] % mod;

    return 0;
}