# include <cstdio>
# include <cstring>

typedef long long ll ;
const char *FIN = "calcul.in", *FOU = "calcul.out";

char A[100005], B[50005], b[200020], sir[10] ;
int C, c ;
ll a, sol, pow ;

int main (void) {
    fscanf (fopen (FIN, "r"), "%s %s %d", A, B, &C) ;
    int i, j, k;
    for (i = strlen(A) - 1, a = j = 0, c = 1; i + 1 && j < C; --i, ++j, c *= 10)
        a += c * (A[i] - '0') ;
    for ( ; j < C; c *= 10, ++j);
    for (i = 0, j = strlen (B), k = 0; i < j; ++i) {
        B[i] -= (B[i] >= 'A' && B[i] <= 'Z') ? 'A' - 10 : '0' ;
        b[++k] = B[i] >> 3, b[++k] = B[i] >> 2 & 1, b[++k] = B[i] >> 1 & 1, b[++k] = B[i] & 1;
    }
    for (pow = i = 1; i <= k; ++i) {
        sol *= ((pow + 1) % c), sol %= c;
		pow *= pow, pow %= c;
        if (b[i] == 1)
            sol = (a * ((sol + 1) % c)) % c, pow *= a, pow %= c ;
    }
    sprintf (sir, "%%0%dlld", C) ;
    fprintf (fopen (FOU, "w"), sir, sol) ;
}