#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 = max (1,lun-c+1); i <= lun; i ++){
        a[1] = a[1] * 10 + auxa[i] - '0';
    }

    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[x] == 0 && x <= biti) {
        x ++;
    }
    int y = 1;
    v[1] = a[1];
    for (int i = 1, j = biti; j >= x; i++, j --) {
        a[i] = (1LL * a[i-1] * a[i-1])% mod;
        if (b[j] == 0) {
            v[i] = (v[i-1] + (1LL*a[i-1] * v[i-1]) % mod) % mod;
        }
        else {
            v[i] = (v[i-1] + (1LL*a[i-1] * a[1]) % mod + (1LL*a[i-1] * a[1] * v[i-1]) % mod ) % mod;
        }
    }
    out << v[biti] % mod;

    return 0;
}