human
Compute n ! under modulo p | Returns largest power of p that divides n !.
Initialize result.
Calculate x = n / p + n / ( p ^ 2 ) + n / ( p ^ 3 ) + ... ..
Utility function to do modular exponentiation . It returns ( x ^ y ) % p.
Initialize result 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.
Returns n ! % p.
Use Sieve of Eratosthenes to find all primes smaller than n.
Consider all primes found by Sieve.
Find the largest power of prime ' i ' that divides n.
Multiply result with ( i ^ k ) % p.
Driver code"
Solution in Python:
assistant
#Here is code to compute n ! under modulo p and the other steps required.
 def largestPower ( n , p ) :
	x = 0
	while ( n ) :
		n //= p
		x += n
	return x
def power ( x , y , p ) :
	res = 1
	x = x % p
	while ( y > 0 ) :
		if ( y & 1 ) :
			res = ( res * x ) % p
		x = ( x * x ) % p
	return res
def modFact ( n , p ) :
	if ( n >= p ) :
		return 0
	res = 1
	isPrime = [ 1 ] * ( n + 1 )
	i = 2
	while ( i * i <= n ) :
		if ( isPrime [ i ] ) :
			for j in range ( 2 * i , n , i ) :
				isPrime [ j ] = 0
		i += 1
	for i in range ( 2 , n ) :
		if ( isPrime [ i ] ) :
			k = largestPower ( n , i )
			res = ( res * power ( i , k , p ) ) % p
	return res
if __name__ == " _ _ main _ _ " :
	n = 25
	p = 29
	print ( modFact ( n , p ) )