A Function to find pow ( base , exponent ) % MOD in log ( exponent ) time
static int modPow ( int Base , int exponent ) { if ( exponent == 0 ) { return 1 ; } if ( exponent == 1 ) { return Base ; } 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 ; } }