# Compute n! under modulo p

Given a large number n and a prime p, how to efficiently compute n! % p?

Examples :

```Input:  n = 5, p = 13
Output: 3
5! = 120 and 120 % 13 = 3

Input:  n = 6, p = 11
Output: 5
6! = 720 and 720 % 11 = 5
```

A Naive Solution is to first compute n!, then compute n! % p. This solution works fine when the value of n! is small. The value of n! % p is generally needed for large values of n when n! cannot fit in a variable, and causes overflow. So computing n! and then using modular operator is not a good idea as there will be overflow even for slightly larger values of n and r.

Following are different methods.

Method 1 (Simple)
A Simple Solution is to one by one multiply result with i under modulo p. So the value of result doesn’t go beyond p before next iteration.

## C++

 `// Simple method to compute n! % p ` `#include ` `using` `namespace` `std; ` ` `  `// Returns value of n! % p ` `int` `modFact(``int` `n, ``int` `p) ` `{ ` `    ``if` `(n >= p) ` `        ``return` `0; ` ` `  `    ``int` `result = 1; ` `    ``for` `(``int` `i = 1; i <= n; i++) ` `        ``result = (result * i) % p; ` ` `  `    ``return` `result; ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``int` `n = 25, p = 29; ` `    ``cout << modFact(n, p); ` `    ``return` `0; ` `} `

## Java

 `// Simple method to compute n! % p ` `import` `java.io.*; ` ` `  `class` `GFG  ` `{ ` `    ``// Returns value of n! % p ` `    ``static` `int` `modFact(``int` `n, ` `                       ``int` `p) ` `    ``{ ` `        ``if` `(n >= p) ` `            ``return` `0``; ` `     `  `        ``int` `result = ``1``; ` `        ``for` `(``int` `i = ``1``; i <= n; i++) ` `            ``result = (result * i) % p; ` `     `  `        ``return` `result; ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `n = ``25``, p = ``29``; ` `        ``System.out.print(modFact(n, p)); ` `    ``} ` `} ` ` `  `// This code is contributed ` `// by aj_36 `

## Python3

 `# Simple method to compute n ! % p ` ` `  `# Returns value of n ! % p ` `def` `modFact(n, p): ` `    ``if` `n >``=` `p: ` `        ``return` `0`     ` `  `    ``result ``=` `1` `    ``for` `i ``in` `range``(``1``, n ``+` `1``): ` `        ``result ``=` `(result ``*` `i) ``%` `p  ` ` `  `    ``return` `result ` ` `  `# Driver Code ` `n ``=` `25``; p ``=` `29` `print` `(modFact(n, p)) ` ` `  `# This code is contributed by Shreyanshi Arun. `

## C#

 `// Simple method to compute n! % p ` `using` `System; ` `  `  `class` `GFG { ` `      `  `    ``// Returns value of n! % p ` `    ``static` `int` `modFact(``int` `n, ``int` `p) ` `    ``{ ` `        ``if` `(n >= p) ` `            ``return` `0; ` `     `  `        ``int` `result = 1; ` `        ``for` `(``int` `i = 1; i <= n; i++) ` `            ``result = (result * i) % p; ` `     `  `        ``return` `result; ` `    ``} ` `     `  `    ``// Driver program ` `    ``static` `void` `Main() ` `    ``{ ` `        ``int` `n = 25, p = 29; ` `        ``Console.Write(modFact(n, p)); ` `    ``} ` `} ` ` `  `// This code is contributed by Anuj_67 `

## PHP

 `= ``\$p``) ` `    ``return` `0;  ` ` `  `    ``\$result` `= 1; ` `    ``for` `(``\$i` `= 1; ``\$i` `<= ``\$n``; ``\$i``++) ` `        ``\$result` `= (``\$result` `* ``\$i``) % ``\$p``;  ` ` `  `    ``return` `\$result``; ` `} ` ` `  `// Driver Code ` `\$n` `= 25; ``\$p` `= 29; ` `echo` `modFact(``\$n``, ``\$p``); ` ` `  `// This code is contributed by Ajit. ` `?> `

Output :

`5`

Time Complexity of this solution is O(n).

Method 2 (Using Sieve)
The idea is based on below formula discussed here.

```The largest possible power of a prime pi that divides n is,
⌊n/pi⌋ + ⌊n/(pi2)⌋ +  ⌊n/(pi3)⌋ + .....+ 0

Every integer can be written as multiplication of powers of primes.  So,
n! = p1k1 * p2k2 * p3k3 * ....
Where p1, p2, p3, .. are primes and
k1, k2, k3, .. are integers greater than or equal to 1.```

The idea is to find all primes smaller than n using Sieve of Eratosthenes. For every prime ‘pi‘, find the largest power of it that divides n!. Let the largest power be ki. Compute piki % p using modular exponentiation. Multiply this with final result under modulo p.

Below is implementation of above idea.

## C++

 `// C++ program to Returns n % p  ` `// using Sieve of Eratosthenes ` `#include ` `using` `namespace` `std; ` ` `  `// Returns largest power of p that divides n! ` `int` `largestPower(``int` `n, ``int` `p) ` `{ ` `    ``// Initialize result ` `    ``int` `x = 0; ` ` `  `    ``// Calculate x = n/p + n/(p^2) + n/(p^3) + .... ` `    ``while` `(n) { ` `        ``n /= p; ` `        ``x += n; ` `    ``} ` `    ``return` `x; ` `} ` ` `  `// Utility function to do modular exponentiation. ` `// It returns (x^y) % p ` `int` `power(``int` `x, ``int` `y, ``int` `p) ` `{ ` `    ``int` `res = 1; ``// Initialize result ` `    ``x = x % p; ``// Update x if it is more than or ` `    ``// equal to p ` `    ``while` `(y > 0) { ` `        ``// If y is odd, multiply x with result ` `        ``if` `(y & 1) ` `            ``res = (res * x) % p; ` ` `  `        ``// y must be even now ` `        ``y = y >> 1; ``// y = y/2 ` `        ``x = (x * x) % p; ` `    ``} ` `    ``return` `res; ` `} ` ` `  `// Returns n! % p ` `int` `modFact(``int` `n, ``int` `p) ` `{ ` `    ``if` `(n >= p) ` `        ``return` `0; ` ` `  `    ``int` `res = 1; ` ` `  `    ``// Use Sieve of Eratosthenes to find all primes ` `    ``// smaller than n ` `    ``bool` `isPrime[n + 1]; ` `    ``memset``(isPrime, 1, ``sizeof``(isPrime)); ` `    ``for` `(``int` `i = 2; i * i <= n; i++) { ` `        ``if` `(isPrime[i]) { ` `            ``for` `(``int` `j = 2 * i; j <= n; j += i) ` `                ``isPrime[j] = 0; ` `        ``} ` `    ``} ` ` `  `    ``// Consider all primes found by Sieve ` `    ``for` `(``int` `i = 2; i <= n; i++) { ` `        ``if` `(isPrime[i]) { ` `            ``// Find the largest power of prime 'i' that divides n ` `            ``int` `k = largestPower(n, i); ` ` `  `            ``// Multiply result with (i^k) % p ` `            ``res = (res * power(i, k, p)) % p; ` `        ``} ` `    ``} ` `    ``return` `res; ` `} ` ` `  `// Driver method ` `int` `main() ` `{ ` `    ``int` `n = 25, p = 29; ` `    ``cout << modFact(n, p); ` `    ``return` `0; ` `} `

## Java

 `import` `java.util.Arrays; ` ` `  `// Java program Returns n % p using Sieve of Eratosthenes ` `public` `class` `GFG { ` ` `  `// Returns largest power of p that divides n! ` `    ``static` `int` `largestPower(``int` `n, ``int` `p) { ` `        ``// Initialize result ` `        ``int` `x = ``0``; ` ` `  `        ``// Calculate x = n/p + n/(p^2) + n/(p^3) + .... ` `        ``while` `(n > ``0``) { ` `            ``n /= p; ` `            ``x += n; ` `        ``} ` `        ``return` `x; ` `    ``} ` ` `  `// Utility function to do modular exponentiation. ` `// It returns (x^y) % p ` `    ``static` `int` `power(``int` `x, ``int` `y, ``int` `p) { ` `        ``int` `res = ``1``; ``// Initialize result ` `        ``x = x % p; ``// Update x if it is more than or ` `        ``// equal to p ` `        ``while` `(y > ``0``) { ` `            ``// If y is odd, multiply x with result ` `            ``if` `(y % ``2` `== ``1``) { ` `                ``res = (res * x) % p; ` `            ``} ` ` `  `            ``// y must be even now ` `            ``y = y >> ``1``; ``// y = y/2 ` `            ``x = (x * x) % p; ` `        ``} ` `        ``return` `res; ` `    ``} ` ` `  `// Returns n! % p ` `    ``static` `int` `modFact(``int` `n, ``int` `p) { ` `        ``if` `(n >= p) { ` `            ``return` `0``; ` `        ``} ` ` `  `        ``int` `res = ``1``; ` ` `  `        ``// Use Sieve of Eratosthenes to find all primes ` `        ``// smaller than n ` `        ``boolean` `isPrime[] = ``new` `boolean``[n + ``1``]; ` `        ``Arrays.fill(isPrime, ``true``); ` `        ``for` `(``int` `i = ``2``; i * i <= n; i++) { ` `            ``if` `(isPrime[i]) { ` `                ``for` `(``int` `j = ``2` `* i; j <= n; j += i) { ` `                    ``isPrime[j] = ``false``; ` `                ``} ` `            ``} ` `        ``} ` ` `  `        ``// Consider all primes found by Sieve ` `        ``for` `(``int` `i = ``2``; i <= n; i++) { ` `            ``if` `(isPrime[i]) { ` `                ``// Find the largest power of prime 'i' that divides n ` `                ``int` `k = largestPower(n, i); ` ` `  `                ``// Multiply result with (i^k) % p ` `                ``res = (res * power(i, k, p)) % p; ` `            ``} ` `        ``} ` `        ``return` `res; ` `    ``} ` ` `  `// Driver method ` `    ``static` `public` `void` `main(String[] args) { ` `        ``int` `n = ``25``, p = ``29``; ` `        ``System.out.println(modFact(n, p)); ` ` `  `    ``} ` `} ` `// This code is contributed by Rajput-Ji `

## Python3

 `# Python3 program to Returns n % p  ` `# using Sieve of Eratosthenes ` ` `  `# Returns largest power of p that divides n!  ` `def` `largestPower(n, p): ` `     `  `    ``# Initialize result  ` `    ``x ``=` `0` `     `  `    ``# Calculate x = n/p + n/(p^2) + n/(p^3) + ....  ` `    ``while` `(n): ` `        ``n ``/``/``=` `p ` `        ``x ``+``=` `n  ` `    ``return` `x  ` ` `  `# Utility function to do modular exponentiation.  ` `# It returns (x^y) % p  ` `def` `power( x, y, p): ` `    ``res ``=` `1` `# Initialize result  ` `    ``x ``=` `x ``%` `p ``# Update x if it is more than  ` `              ``# or equal to p  ` `    ``while` `(y > ``0``) :  ` `         `  `        ``# If y is odd, multiply x with result  ` `        ``if` `(y & ``1``) : ` `            ``res ``=` `(res ``*` `x) ``%` `p  ` ` `  `        ``# y must be even now  ` `        ``y ``=` `y >> ``1` `# y = y/2  ` `        ``x ``=` `(x ``*` `x) ``%` `p  ` ` `  `    ``return` `res  ` ` `  `# Returns n! % p  ` `def` `modFact( n, p) : ` ` `  `    ``if` `(n >``=` `p) : ` `        ``return` `0` ` `  `    ``res ``=` `1` ` `  `    ``# Use Sieve of Eratosthenes to find  ` `    ``# all primes smaller than n  ` `    ``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` `         `  `    ``# Consider all primes found by Sieve  ` `    ``for` `i ``in` `range``(``2``, n):  ` `        ``if` `(isPrime[i]) : ` `             `  `            ``# Find the largest power of prime 'i' ` `            ``# that divides n  ` `            ``k ``=` `largestPower(n, i)  ` ` `  `            ``# Multiply result with (i^k) % p  ` `            ``res ``=` `(res ``*` `power(i, k, p)) ``%` `p  ` ` `  `    ``return` `res  ` ` `  `# Driver code  ` `if` `__name__ ``=``=``"__main__"``: ` `    ``n ``=` `25` `    ``p ``=` `29` `    ``print``(modFact(n, p)) ` ` `  `# This code is contributed by ` `# Shubham Singh(SHUBHAMSINGH10) `

## C#

 `// C# program Returns n % p using Sieve of Eratosthenes  ` `using` `System; ` ` `  ` `  `public` `class` `GFG {  ` ` `  `// Returns largest power of p that divides n!  ` `    ``static` `int` `largestPower(``int` `n, ``int` `p) {  ` `        ``// Initialize result  ` `        ``int` `x = 0;  ` ` `  `        ``// Calculate x = n/p + n/(p^2) + n/(p^3) + ....  ` `        ``while` `(n > 0) {  ` `            ``n /= p;  ` `            ``x += n;  ` `        ``}  ` `        ``return` `x;  ` `    ``}  ` ` `  `// Utility function to do modular exponentiation.  ` `// It returns (x^y) % p  ` `    ``static` `int` `power(``int` `x, ``int` `y, ``int` `p) {  ` `        ``int` `res = 1; ``// Initialize result  ` `        ``x = x % p; ``// Update x if it is more than or  ` `        ``// equal to p  ` `        ``while` `(y > 0) {  ` `            ``// If y is odd, multiply x with result  ` `            ``if` `(y % 2 == 1) {  ` `                ``res = (res * x) % p;  ` `            ``}  ` ` `  `            ``// y must be even now  ` `            ``y = y >> 1; ``// y = y/2  ` `            ``x = (x * x) % p;  ` `        ``}  ` `        ``return` `res;  ` `    ``}  ` ` `  `// Returns n! % p  ` `    ``static` `int` `modFact(``int` `n, ``int` `p) {  ` `        ``if` `(n >= p) {  ` `            ``return` `0;  ` `        ``}  ` ` `  `        ``int` `res = 1;  ` ` `  `        ``// Use Sieve of Eratosthenes to find all primes  ` `        ``// smaller than n  ` `        ``bool` `[]isPrime = ``new` `bool``[n + 1];  ` `        ``for``(``int` `i = 0;i

## PHP

0)
{
// If y is odd, multiply x with result
if (\$y & 1)
\$res = (\$res * \$x) % \$p;

// y must be even now
\$y = \$y >> 1; // y = y/2
\$x = (\$x * \$x) % \$p;
}
return \$res;
}

// Returns n! % p
function modFact(\$n, \$p)
{
if (\$n >= \$p)
return 0;

\$res = 1;

// Use Sieve of Eratosthenes to find
// all primes smaller than n
\$isPrime = array_fill(0, \$n + 1, true);
for (\$i = 2; \$i * \$i <= \$n; \$i++) { if (\$isPrime[\$i]) { for (\$j = 2 * \$i; \$j <= \$n; \$j += \$i) \$isPrime[\$j] = 0; } } // Consider all primes found by Sieve for (\$i = 2; \$i <= \$n; \$i++) { if (\$isPrime[\$i]) { // Find the largest power of // prime 'i' that divides n \$k = largestPower(\$n, \$i); // Multiply result with (i^k) % p \$res = (\$res * power(\$i, \$k, \$p)) % \$p; } } return \$res; } // Driver Code \$n = 25; \$p = 29; echo modFact(\$n, \$p); // This code is contributed by mits ?>

Output:

`5`

This is an interesting method, but time complexity of this is more than Simple Method as time complexity of Sieve itself is O(n log log n). This method can be useful if we have list of prime numbers smaller than or equal to n available to us.

Method 3 (Using Wilson’s Theorem)
Wilson’s theorem states that a natural number p > 1 is a prime number if and only if

```    (p - 1) ! ≡ -1   mod p
OR  (p - 1) ! ≡  (p-1) mod p ```

Note that n! % p is 0 if n >= p. This method is mainly useful when p is close to input number n. For example (25! % 29). From Wilson’s theorem, we know that 28! is -1. So we basically need to find [ (-1) * inverse(28, 29) * inverse(27, 29) * inverse(26) ] % 29. The inverse function inverse(x, p) returns inverse of x under modulo p (See this for details).

## C++

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

## Java

 `// Java program to compute n! % p  ` `// using Wilson's Theorem ` `class` `GFG ` `{ ` `     `  `// Utility function to do ` `// modular exponentiation. ` `// It returns (x^y) % p ` `static` `int` `power(``int` `x, ``int` `y, ``int` `p) ` `{ ` `    ``int` `res = ``1``; ``// Initialize result ` `    ``x = x % p;   ``// Update x if it is more  ` `                 ``// than or equal to p ` `    ``while` `(y > ``0``)  ` `    ``{ ` `        ``// If y is odd, multiply  ` `        ``// x with result ` `        ``if` `((y & ``1``) > ``0``) ` `            ``res = (res * x) % p; ` ` `  `        ``// y must be even now ` `        ``y = y >> ``1``; ``// y = y/2 ` `        ``x = (x * x) % p; ` `    ``} ` `    ``return` `res; ` `} ` ` `  `// Function to find modular ` `// inverse of a under modulo p ` `// using Fermat's method.  ` `// Assumption: p is prime ` `static` `int` `modInverse(``int` `a, ``int` `p) ` `{ ` `    ``return` `power(a, p - ``2``, p); ` `} ` ` `  `// Returns n! % p using  ` `// Wilson's Theorem ` `static` `int` `modFact(``int` `n, ``int` `p) ` `{ ` `    ``// n! % p is 0 if n >= p ` `    ``if` `(p <= n) ` `        ``return` `0``; ` ` `  `    ``// Initialize result as (p-1)!  ` `    ``// which is -1 or (p-1) ` `    ``int` `res = (p - ``1``); ` ` `  `    ``// Multiply modulo inverse of ` `    ``// all numbers from (n+1) to p ` `    ``for` `(``int` `i = n + ``1``; i < p; i++) ` `        ``res = (res * modInverse(i, p)) % p; ` `    ``return` `res; ` `} ` ` `  `// Driver Code ` `public` `static` `void` `main(String[] args) ` `{ ` `    ``int` `n = ``25``, p = ``29``; ` `    ``System.out.println(modFact(n, p)); ` `} ` `} ` ` `  `// This code is contributed by mits `

## Python3

 `# Python3 program to comput  ` `# n! % p using Wilson's Theorem ` ` `  `# Utility function to do modular  ` `# exponentiation. It returns (x^y) % p ` `def` `power(x, y,p): ` ` `  `    ``res ``=` `1``; ``# Initialize result ` `    ``x ``=` `x ``%` `p; ``# Update x if it is more  ` `               ``# than or equal to p ` `    ``while` `(y > ``0``): ` `         `  `        ``# If y is odd, multiply  ` `        ``# x with result ` `        ``if` `(y & ``1``): ` `            ``res ``=` `(res ``*` `x) ``%` `p; ` ` `  `        ``# y must be even now ` `        ``y ``=` `y >> ``1``; ``# y = y/2 ` `        ``x ``=` `(x ``*` `x) ``%` `p; ` `     `  `    ``return` `res ` ` `  `# Function to find modular inverse  ` `# of a under modulo p using Fermat's ` `# method. Assumption: p is prime ` `def` `modInverse(a, p): ` ` `  `    ``return` `power(a, p ``-` `2``, p) ` `     `  `# Returns n! % p using  ` `# Wilson's Theorem ` `def` `modFact(n , p): ` ` `  `    ``# n! % p is 0 if n >= p ` `    ``if` `(p <``=` `n): ` `        ``return` `0` ` `  `    ``# Initialize result as (p-1)! ` `    ``# which is -1 or (p-1) ` `    ``res ``=` `(p ``-` `1``) ` ` `  `    ``# Multiply modulo inverse of  ` `    ``# all numbers from (n+1) to p ` `    ``for` `i ``in` `range` `(n ``+` `1``, p): ` `        ``res ``=` `(res ``*` `modInverse(i, p)) ``%` `p ` `    ``return` `res ` ` `  `# Driver code ` `n ``=` `25` `p ``=` `29` `print``(modFact(n, p)) ` ` `  `# This code is contributed by ihritik `

## C#

 `// C# program to comput n! % p  ` `// using Wilson's Theorem ` `using` `System; ` ` `  `// Utility function to do modular  ` `// exponentiation. It returns (x^y) % p ` `class` `GFG ` `{ ` `public` `int` `power(``int` `x, ``int` `y, ``int` `p) ` `{ ` `    ``int` `res = 1; ``// Initialize result ` `    ``x = x % p; ``// Update x if it is more  ` `               ``// than or equal to p ` `    ``while` `(y > 0)  ` `    ``{ ` `        ``// If y is odd, multiply ` `        ``// x with result ` `        ``if``((y & 1) > 0) ` `            ``res = (res * x) % p; ` ` `  `        ``// y must be even now ` `        ``y = y >> 1; ``// y = y/2 ` `        ``x = (x * x) % p; ` `    ``} ` `    ``return` `res; ` `} ` ` `  `// Function to find modular inverse  ` `// of a under modulo p using Fermat's ` `// method. Assumption: p is prime ` `public` `int` `modInverse(``int` `a, ``int` `p) ` `{ ` `    ``return` `power(a, p - 2, p); ` `} ` ` `  `// Returns n! % p using  ` `// Wilson's Theorem ` `public` `int` `modFact(``int` `n, ``int` `p) ` `{ ` `    ``// n! % p is 0 if n >= p ` `    ``if` `(p <= n) ` `        ``return` `0; ` ` `  `    ``// Initialize result as (p-1)! ` `    ``// which is -1 or (p-1) ` `    ``int` `res = (p - 1); ` ` `  `    ``// Multiply modulo inverse of all  ` `    ``// numbers from (n+1) to p ` `    ``for` `(``int` `i = n + 1; i < p; i++) ` `        ``res = (res * modInverse(i, p)) % p; ` `    ``return` `res; ` `} ` ` `  `// Driver method ` `public` `static` `void` `Main() ` `{ ` `    ``GFG g = ``new` `GFG(); ` `    ``int` `n = 25, p = 29; ` `    ``Console.WriteLine(g.modFact(n, p)); ` `} ` `} ` ` `  `// This code is contributed by Soumik `

## PHP

 ` 0)  ` `    ``{ ` `        ``// If y is odd, multiply ` `        ``// x with result ` `        ``if` `(``\$y` `& 1) ` `            ``\$res` `= (``\$res` `* ``\$x``) % ``\$p``; ` ` `  `        ``// y must be even now ` `        ``\$y` `= ``\$y` `>> 1; ``// y = y/2 ` `        ``\$x` `= (``\$x` `* ``\$x``) % ``\$p``; ` `    ``} ` `    ``return` `\$res``; ` `} ` ` `  `// Function to find modular  ` `// inverse of a under modulo  ` `// p using Fermat's method.  ` `// Assumption: p is prime ` `function` `modInverse(``\$a``, ``\$p``) ` `{ ` `    ``return` `power(``\$a``, ``\$p` `- 2, ``\$p``); ` `} ` ` `  `// Returns n! % p  ` `// using Wilson's Theorem ` `function` `modFact( ``\$n``, ``\$p``) ` `{ ` `    ``// n! % p is 0 ` `    ``// if n >= p ` `    ``if` `(``\$p` `<= ``\$n``) ` `        ``return` `0; ` ` `  `    ``// Initialize result as  ` `    ``// (p-1)! which is -1 or (p-1) ` `    ``\$res` `= (``\$p` `- 1); ` ` `  `    ``// Multiply modulo inverse  ` `    ``// of all numbers from (n+1) ` `    ``// to p ` `    ``for` `(``\$i` `= ``\$n` `+ 1; ``\$i` `< ``\$p``; ``\$i``++) ` `        ``\$res` `= (``\$res` `*  ` `                ``modInverse(``\$i``, ``\$p``)) % ``\$p``; ` `    ``return` `\$res``; ` `} ` ` `  `// Driver Code ` `\$n` `= 25; ``\$p` `= 29; ` `echo` `modFact(``\$n``, ``\$p``); ` ` `  `// This code is contributed by ajit ` `?> `

Output:

`5`

Time complexity of this method is O((p-n)*Logn)

Method 4 (Using Primality Test Algorithm)

```1) Initialize: result = 1
2) While n is not prime
result = (result * n) % p
3) result = (result * (n-1)) % p  // Using Wilson's Theorem
4) Return result.```

Note that time complexity step 2 of above algorithm depends on the primality test algorithm being used and value of the largest prime smaller than n. The AKS algorithm for example takes O(Log 10.5 n) time.