#include <bits/stdc++.h>

using namespace std;

char a[100010], b[50010], bit[200010];
int la, lb, lbit, uca;
int c;

void processB()
{
    lbit = 0;
    for(int i = 0; i < lb; i++)
    {
        int nr = 0;
        if(isdigit(b[i]))
            nr = b[i] - '0';
        else nr = b[i] - 'A' + 10;
        for(int j = 3; j >= 0; j--)
            bit[lbit++] = (nr >> j) & 1;
    }
}

int main()
{
    freopen("calcul.in", "r", stdin);
    freopen("calcul.out", "w", stdout);
    gets(a);
    gets(b);
    scanf("%d", &c);
    la = strlen(a); lb = strlen(b);
    if (a[la - 1] == '\n') a[la - 1] = 0, la--;
    if (b[lb - 1] == '\n') b[lb - 1] = 0, lb--;
    processB();
    int MOD = 1;
    for(int i = 0; i < c; i++)
        MOD *= 10;
    uca = 0;
    for(int i = max(0, la - c); i < la; i++)
        uca = uca * 10 + a[i] - '0';
    int s = 0, p = 1;
    for(int i = 0; i < lbit; i++)
    {
        s = 1LL * s * (1 + p) % MOD;
        p = 1LL * p * p % MOD;
        if(bit[i])
        {
            p = 1LL * p * uca % MOD;
            s = 1LL * (p + s) % MOD;
        }
    }
    char cif[13];
    for(int i = c - 1; i >= 0; i--)
    {
        cif[i] = s % 10 + '0';
        s /= 10;
    }
    cif[c] = 0;
    puts(cif);
    return 0;
}