Compute n ! under modulo p | Utility function to do modular exponentiation . It returns ( x ^ y ) % p ; $res = 1 ; Initialize result $x = $x % $p ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now $y = $y >> 1 ; y = y / 2 ; Function to find modular inverse of a under modulo p using Fermat 's method. Assumption: p is prime ; Returns n ! % p using Wilson 's Theorem ; n ! % p is 0 if n >= p ; Initialize result as ( p - 1 ) ! which is - 1 or ( p - 1 ) ; Multiply modulo inverse of all numbers from ( n + 1 ) to p ; Driver Code
< ? php function power ( $ x , $ y , $ p ) { while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ p ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } function modInverse ( $ a , $ p ) { return power ( $ a , $ p - 2 , $ p ) ; } function modFact ( $ n , $ p ) { if ( $ p <= $ n ) return 0 ; $ res = ( $ p - 1 ) ; for ( $ i = $ n + 1 ; $ i < $ p ; $ i ++ ) $ res = ( $ res * modInverse ( $ i , $ p ) ) % $ p ; return $ res ; } $ n = 25 ; $ p = 29 ; echo modFact ( $ n , $ p ) ; ? >