#include <fstream>
#include <cstring>

using namespace std;

char A[100004], B[50004];
bool bin[200004];

inline int Max(int a, int b)
{
    if (a > b)
        return a;
    return b;
}

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

    int c;
    in >> A;
    in >> B;
    in >> c;

    long long a = 0;
    for (int i = Max(strlen(A) - c, 0); i < strlen(A); i++)
        a = a * 10 + A[i] - '0';

    int lenb = strlen(B);
    for (int x, i = 0; i < lenb; i++)
    {
        if (B[i] >= '0' && B[i] <= '9')
            x = B[i] - '0';
        else
            x = B[i] - 'a' + 10;
        if (x & 1<<3)
            bin[i*4] = 1;
        if (x & 1<<2)
            bin[i*4+1] = 1;
        if (x & 1<<1)
            bin[i*4+2] = 1;
        if (x & 1)
            bin[i*4+3] = 1;
    }

    long long mod = 1;
    for (int i = 1; i <= c; i++)
        mod *= 10;

    long long result = 0;
    long long k = a;
    long long l = a;
    lenb *= 4;
    for (int i = lenb - 1; i >= 0; i--)
    {
        if (bin[i])
            result = (result * k + l) % mod;
        l = (l * (k+1)) % mod;
        k = (k * k) % mod;
    }

    mod /= 10;
    while (result < mod && mod > 1)
    {
        out << 0;
        mod /= 10;
    }

    out << result << '\n';

    return 0;
}