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