pow2.c

#include <stdio.h>
#define MOD 10000

int my_pow(int N, int P) {
    if (P == 0) return 1;
    if (P == 1) return (N % MOD);

    int temp_pow = my_pow(N, P/2);

    if ((P % 2) == 0) {
        return (temp_pow * temp_pow) % MOD;
    }

    return (((temp_pow * temp_pow) % MOD) * (N % MOD)) % MOD;
}

int main(int argc, char const *argv[]) {
    int N, P;

    scanf("%d %d", &N, &P);
    printf("%d\n", my_pow(N,P));

    return 0;
}