Function to return base ^ exponent
static int expo ( int Base , int exponent ) { int ans = 1 ; while ( exponent != 0 ) { if ( ( exponent & 1 ) == 1 ) { ans = ans * Base ; ans = ans % mod ; } Base = Base * Base ; Base %= mod ; exponent >>= 1 ; } return ans % mod ; }