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

using namespace std;

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

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

    unsigned long long int x = 0;
    long long i, j;
    int c;
    fgets(input, 100004, 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, 50004, 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", &c);
    for (i = 0; i < c; ++i)
        MOD *= 10;

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

    x %= MOD;

    j = 0;
    unsigned 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;

    }
    char format[8];
    format[0] = '%';
    format[1] = '0';
    format[2] = c + '0';
    format[3] = format[4] = 'l';
    format[5] = 'u';
    format[6] = '\n';
    format[7] = 0;
    /*if (rasp / MOD)*/
        fprintf(fout, format, rasp % MOD);
    /*else
        fprintf(fout, "%lld\n", rasp % MOD);*/

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