Big number MOD function.

(A*B) % MOD = ((A % MOD) * (B % MOD)) % MOD

So

(A^n) % MOD = (((A ^ (n/2)) % MOD) * ((A ^ (n/2)) % MOD)) % MOD;

function is:

int cal(int pow, int val, int MOD) {
    if(pow == 0)
        return 1;
    int v = cal(pow/2, val, MOD);
    if(pow % 2 == 0)
        return (v*v) % MOD;
    else
        return (((v*val) % MOD) * v) % MOD;
}