Recursive function to return ( x ^ n ) % m
function modexp ( $ x , $ n ) { $ m = 1000000007 ; if ( $ n == 0 ) { return 1 ; } else if ( $ n % 2 == 0 ) { return modexp ( ( $ x * $ x ) % $ m , $ n / 2 ) ; } else { return ( $ x * modexp ( ( $ x * $ x ) % $ m , ( $ n - 1 ) / 2 ) % $ m ) ; } }