A Function to find pow ( base , exponent ) % MOD in log ( exponent ) time
unsigned long long int modPow ( unsigned long long int base , unsigned long long int exponent ) { if ( exponent == 0 ) return 1 ; if ( exponent == 1 ) return base ; unsigned long long int temp = modPow ( base , exponent / 2 ) ; if ( exponent % 2 == 0 ) return ( temp % MOD * temp % MOD ) % MOD ; else return ( ( ( temp % MOD * temp % MOD ) % MOD ) * base % MOD ) % MOD ; }