#include <cstring>
#include <fstream>
#include <algorithm>

using namespace std;

int MOD;

int N, M, C, X;
char A[100010], B[50010];
bool wh[200002];

int main()
{
    ifstream fin("calcul.in");
    ofstream fout("calcul.out");

    fin >> (A + 1);
    N = strlen(A + 1);

    fin >> (B + 1);
    M = strlen(B + 1);

    fin >> C;

    MOD = 1;
    for (int i = 1; i <= C; ++i)
        MOD *= 10;

    for (int i = max(1, N - C + 1); i <= N; ++i)
        X = X * 10 + (A[i] - '0');

    for (int i = M; i >= 1; --i)
    {
        int pnow;
        if (B[i] >= '0' && B[i] <= '9')
            pnow = B[i] - '0';
        else
            pnow = 10 + B[i] - 'A';

        for (int j = 0; j < 4; ++j)
            wh[(M - i) * 4 + j + 1] = ((pnow & (1 << j)) != 0);
    }

    M *= 4;

    int Anow = X, Snow = X, result = 0;
    for (int i = 1; i <= M; ++i)
    {
        if (wh[i] == 1) result = (1LL * result * Anow + Snow) % MOD;
        Snow = 1LL * Snow * (Anow + 1) % MOD;
        Anow = 1LL * Anow * Anow % MOD;
    }

    int numcif = 0, aux = result;
    while (aux)
    {
        aux /= 10;
        ++numcif;
    }
    for (int i = 1; i <= C - numcif - (result == 0); ++i)
        fout << 0;
    fout << result << '\n';

    fin.close();
    fout.close();
}