Fast Modular Exponentiation

long pow(long base, int num){
    long res = 1;
    while(num > 0){
        if((num & 1) == 1){
            res *= base;
            res %= mod;
        }
        base *= base;
        base %= mod;
        num >>= 1;
    }
    return res;
}