Function to compute a ^ n % mod
function power ( $ a , $ n ) { global $ mod ; if ( $ n == 0 ) return 1 ; $ p = power ( $ a , $ n / 2 ) % $ mod ; $ p = ( $ p * $ p ) % $ mod ; if ( $ n & 1 ) $ p = ( $ p * $ a ) % $ mod ; return $ p ; }