Q374: Big Mod

/*
    recursive

    terminal condition: P = 0 or P = 1
    if P is odd, B^P = B^(p-1)*B
    if P is even, B^P = B^(P/2) * B^(P/2)

    Run time: 0.010
*/
#include <stdio.h>
long long int compute(int B, int P, int M);

int main()
{
    int B, P, M;
    long long int remainder;

    while (scanf("%d%d%d", &B, &P, &M) == 3)
    {
        remainder = compute(B, P, M);
        printf("%lld\n", remainder);
    }

    return 0;
}

long long int compute(int B, int P, int M)
{
    if (!P) return 1;
    if (P == 1) return B;
    else
    if (P%2)
        return (compute(B, P-1, M)*compute(B, 1, M))%M;
    else
        return (compute(B, P/2, M)*compute(B, P/2, M))%M;
}