#include <fstream>
#include <stack>
#include <cstring>

using namespace std;

long int MOD = 1;
char input[100002];
stack<char> s;

int main()
{
    FILE *fin = fopen("calcul.in", "r");
    FILE *fout = fopen("calcul.out", "w");

    long long int x = 0, i, j;
    fgets(input, 100002, fin);
    j = strlen(input) - 1;
    i = j - 10;
    if (i < 0)
        i = 0;
    for (; i < j; ++i)
    {
        x = x * 10 + input[i] - '0';
    }

    fgets(input, 50002, fin);
    for (i = 0; input[i] != '\n'; ++i)
    {
        if (input[i] <= '9') {
            j = input[i] - '0';
            s.push(j & 8);
            s.push(j & 4);
            s.push(j & 2);
            s.push(j & 1);
        } else {
            j = input[i] - 'A' + 10;
            s.push(1);// no need to check
            s.push(j & 4);
            s.push(j & 2);
            s.push(j & 1);
        }
    }
    fscanf(fin, "%d", &j);
    for (i = 0; i < j; ++i)
        MOD *= 10;

    /// Next line for test
    //MOD *= 10000;

    x %= MOD;

    j = 0;
    long long int rasp = 0, y = x;
    while (!s.empty())
    {
        j = s.top();
        s.pop();
        if (j) {
            rasp = (rasp + y) % MOD;
            y = y * ((x * (1 + x)) % MOD) % MOD;
        } else {
            y = y * (1 + x) % MOD;
        }
        x = (x * x) % MOD;

    }
    fprintf(fout, "%lld", rasp % MOD);

    fclose(fin);
    fclose(fout);
    return 0;
}