Function to return base ^ exponent
unsigned long long expo ( unsigned long long base , unsigned long long exponent ) { unsigned long long 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 ; }