function to find moudulo inverse under 10 ^ 9 + 7
< ? php function modInv ( $ x ) { $ MOD = 1000000007 ; $ n = $ MOD - 2 ; $ result = 1 ; while ( $ n ) { if ( $ n & 1 ) $ result = $ result * $ x % $ MOD ; $ x = $ x * $ x % $ MOD ; $ n = $ n / 2 ; } return $ result ; }