Iterative Function to calculate ( x ^ y ) in O ( log y )
function power ( $ x , $ y ) { global $ M ; $ res = 1 ; while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ M ; $ y = ( $ y >> 1 ) % $ M ; $ x = ( $ x * $ x ) % $ M ; } return $ res ; }