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
def power ( x , y , p ) : NEW_LINE INDENT while ( y > 0 ) : NEW_LINE INDENT if ( y & 1 ) : NEW_LINE INDENT res = ( res * x ) % p ; NEW_LINE DEDENT x = ( x * x ) % p ; NEW_LINE DEDENT return res NEW_LINE DEDENT def modInverse ( a , p ) : NEW_LINE INDENT return power ( a , p - 2 , p ) NEW_LINE DEDENT def modFact ( n , p ) : NEW_LINE INDENT if ( p <= n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT res = ( p - 1 ) NEW_LINE for i in range ( n + 1 , p ) : NEW_LINE INDENT res = ( res * modInverse ( i , p ) ) % p NEW_LINE DEDENT return res NEW_LINE DEDENT n = 25 NEW_LINE p = 29 NEW_LINE print ( modFact ( n , p ) ) NEW_LINE