human
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"
How can the above be solved in Python?
assistant
#Here is code to compute n ! under modulo p and the other steps required.
 def power ( x , y , p ) :
	while ( y > 0 ) :
		if ( y & 1 ) :
			res = ( res * x ) % p ;
		x = ( x * x ) % p ;
	return res
def modInverse ( a , p ) :
	return power ( a , p - 2 , p )
def modFact ( n , p ) :
	if ( p <= n ) :
		return 0
	res = ( p - 1 )
	for i in range ( n + 1 , p ) :
		res = ( res * modInverse ( i , p ) ) % p
	return res
n = 25
p = 29
print ( modFact ( n , p ) )