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