#include <iostream>
#include <cstdio>
#include <cstring>
#define NMAX 100005

using namespace std;

char str[NMAX];
bool biti[4 * NMAX];
long long a, c, modulo = 1, v[15];
int lung;

void read()
{
    scanf("%s\n", &str);

    lung = strlen(str);
    long long lungNou = max(0, lung - 9);

    for(long long i = lungNou; i < lung; ++i)
        a = a*10 + str[i] - '0';

    scanf("%s\n", &str);
    lung = strlen(str);

    for(int i = 0; i < lung; ++i)
    {
        long long cifra;

        if(str[i] >= '0' && str[i] <= '9')
            cifra = str[i] - '0';
        else if(str[i] >= 'A' && str[i] <= 'F')
            cifra = str[i] - 'A' + 10;

        for(int j = 0; j < 4; ++j)
        {
            biti[4 * (lung - i - 1) + j + 1] = (cifra & (1<<j));
        }
    }

    scanf("%d", &c);
    for(int i=1; i<=c; ++i)
        modulo *= 10;

    a %= modulo;
}

void solve()
{
    long long rezultat = 0, putereA = a, suma = a;

    for(int i = 1; i <= 4*lung; ++i)
    {
        if(biti[i])
        {
            rezultat = (rezultat * putereA + suma) % modulo;
        }
        suma = ( suma * (1 + putereA) ) % modulo;
        putereA = ( putereA * putereA ) % modulo;
    }

    lung = c;

    while(rezultat)
    {
        v[c--] = rezultat % 10;
        rezultat /= 10;
    }

}

void print()
{
    for(int i=1; i<=lung; ++i)
        printf("%d", v[i]);
}

int main()
{
    freopen("calcul.in", "r", stdin);
    freopen("calcul.out", "w", stdout);
    read();
    solve();
    print();
    return 0;
}