Function to return a raised to the power n with complexity O ( log ( n ) )
long long powmod ( long long a , long long n ) { if ( ! n ) return 1 ; long long pt = powmod ( a , n / 2 ) ; pt = ( pt * pt ) % mod ; if ( n % 2 ) return ( pt * a ) % mod ; else return pt ; }