# Compute nCr % p | Set 3 (Using Fermat Little Theorem)

Given three numbers n, r and p, compute value of nCr mod p. Here p is a prime number greater than n. Here nCr is Binomial Coefficient.

Example:

```Input:  n = 10, r = 2, p = 13
Output: 6
Explanation: 10C2 is 45 and 45 % 13 is 6.

Input:  n = 6, r = 2, p = 13
Output: 2
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We have discussed following methods in previous posts.
Compute nCr % p | Set 1 (Introduction and Dynamic Programming Solution)
Compute nCr % p | Set 2 (Lucas Theorem)

In this post, Fermat Theorem based solution is discussed.

Background:
Fermat’s little theorem and modular inverse
Fermat’s little theorem states that if p is a prime number, then for any integer a, the number ap – a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as:
ap = a (mod p)
For example, if a = 2 and p = 7, 27 = 128, and 128 – 2 = 7 × 18 is an integer multiple of 7.

If a is not divisible by p, Fermat’s little theorem is equivalent to the statement a p – 1 – 1 is an integer multiple of p, i.e
ap-1 = 1 (mod p)

If we multiply both sides by a-1, we get.
ap-2 = a-1 (mod p)

So we can find modular inverse as p-2.

Computation:

```We know the formula for  nCr
nCr = fact(n) / (fact(r) x fact(n-r))
Here fact() means factorial.

nCr % p = (fac[n]* modIverse(fac[r]) % p *
modIverse(fac[n-r]) % p) % p;
Here modIverse() means modular inverse under
modulo p.
```

Following is the implementation of the above algorithm. In the following implementation, an array fac[] is used to store all the computed factorial values.

## C++

 `// A modular inverse based solution to ` `// compute nCr % p ` `#include ` `using` `namespace` `std; ` ` `  `/* Iterative Function to calculate (x^y)%p ` `  ``in O(log y) */` `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^(-1) mod p ` `int` `modInverse(``int` `n, ``int` `p) ` `{ ` `    ``return` `power(n, p-2, p); ` `} ` ` `  `// Returns nCr % p using Fermat's little ` `// theorem. ` `int` `nCrModPFermat(``int` `n, ``int` `r, ``int` `p) ` `{ ` `   ``// Base case ` `   ``if` `(r==0) ` `      ``return` `1; ` ` `  `    ``// Fill factorial array so that we ` `    ``// can find all factorial of r, n ` `    ``// and n-r ` `    ``int` `fac[n+1]; ` `    ``fac = 1; ` `    ``for` `(``int` `i=1 ; i<=n; i++) ` `        ``fac[i] = fac[i-1]*i%p; ` ` `  `    ``return` `(fac[n]* modInverse(fac[r], p) % p * ` `            ``modInverse(fac[n-r], p) % p) % p; ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``// p must be a prime greater than n. ` `    ``int` `n = 10, r = 2, p = 13; ` `    ``cout << ``"Value of nCr % p is "` `         ``<< nCrModPFermat(n, r, p); ` `    ``return` `0; ` `} `

## Java

 `// A modular inverse based solution to ` `// compute nCr %  ` `import` `java .io.*; ` ` `  `class` `GFG { ` `     `  `    ``/* Iterative Function to calculate ` `    ``(x^y)%p in O(log y) */` `    ``static` `int` `power(``int` `x, ``int` `y, ``int` `p) ` `    ``{ ` `         `  `        ``// Initialize result ` `        ``int` `res = ``1``; ` `     `  `        ``// Update x if it is more than or ` `        ``// equal to p ` `        ``x = x % 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^(-1) mod p ` `    ``static` `int` `modInverse(``int` `n, ``int` `p) ` `    ``{ ` `        ``return` `power(n, p-``2``, p); ` `    ``} ` `     `  `    ``// Returns nCr % p using Fermat's ` `    ``// little theorem. ` `    ``static` `int` `nCrModPFermat(``int` `n, ``int` `r, ` `                                    ``int` `p) ` `    ``{ ` `         `  `        ``// Base case ` `        ``if` `(r == ``0``) ` `            ``return` `1``; ` `     `  `        ``// Fill factorial array so that we ` `        ``// can find all factorial of r, n ` `        ``// and n-r ` `        ``int``[] fac = ``new` `int``[n+``1``]; ` `        ``fac[``0``] = ``1``; ` `         `  `        ``for` `(``int` `i = ``1` `;i <= n; i++) ` `            ``fac[i] = fac[i-``1``] * i % p; ` `     `  `        ``return` `(fac[n]* modInverse(fac[r], p) ` `                ``% p * modInverse(fac[n-r], p) ` `                                    ``% p) % p; ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `         `  `        ``// p must be a prime greater than n. ` `        ``int` `n = ``10``, r = ``2``, p = ``13``; ` `        ``System.out.println(``"Value of nCr % p is "` `                ``+ nCrModPFermat(n, r, p)); ` `    ``} ` `} ` ` `  `// This code is contributd by Anuj_67. `

## Python3

 `# Python3 function to  ` `# calculate nCr % p ` `def` `ncr(n, r, p): ` `    ``# initialize numerator ` `    ``# and denominator ` `    ``num ``=` `den ``=` `1`  `    ``for` `i ``in` `range``(r): ` `        ``num ``=` `(num ``*` `(n ``-` `i)) ``%` `p ` `        ``den ``=` `(den ``*` `(i ``+` `1``)) ``%` `p ` `    ``return` `(num ``*` `pow``(den,  ` `            ``p ``-` `2``, p)) ``%` `p ` ` `  `# p must be a prime ` `# greater than n ` `n, r, p ``=` `10``, ``2``, ``13` `print``(``"Value of nCr % p is"``,  ` `               ``ncr(n, r, p)) `

## C#

 `// A modular inverse based solution to ` `// compute nCr % p ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``/* Iterative Function to calculate ` `    ``(x^y)%p in O(log y) */` `    ``static` `int` `power(``int` `x, ``int` `y, ``int` `p) ` `    ``{ ` `         `  `        ``// Initialize result ` `        ``int` `res = 1; ` `     `  `        ``// Update x if it is more than or ` `        ``// equal to p ` `        ``x = x % 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^(-1) mod p ` `    ``static` `int` `modInverse(``int` `n, ``int` `p) ` `    ``{ ` `        ``return` `power(n, p-2, p); ` `    ``} ` `     `  `    ``// Returns nCr % p using Fermat's ` `    ``// little theorem. ` `    ``static` `int` `nCrModPFermat(``int` `n, ``int` `r, ` `                                    ``int` `p) ` `    ``{ ` `         `  `        ``// Base case ` `        ``if` `(r == 0) ` `            ``return` `1; ` `     `  `        ``// Fill factorial array so that we ` `        ``// can find all factorial of r, n ` `        ``// and n-r ` `        ``int``[] fac = ``new` `int``[n+1]; ` `        ``fac = 1; ` `         `  `        ``for` `(``int` `i = 1 ;i <= n; i++) ` `            ``fac[i] = fac[i-1] * i % p; ` `     `  `        ``return` `(fac[n]* modInverse(fac[r], p) ` `                ``% p * modInverse(fac[n-r], p) ` `                                    ``% p) % p; ` `    ``} ` `     `  `    ``// Driver program ` `    ``static` `void` `Main() ` `    ``{ ` `         `  `        ``// p must be a prime greater than n. ` `        ``int` `n = 10, r = 2, p = 13; ` `        ``Console.Write(``"Value of nCr % p is "` `                  ``+ nCrModPFermat(n, r, p)); ` `    ``} ` `} ` ` `  `// This code is contributd by Anuj_67 `

## PHP

 ` 0) ` `    ``{ ` `         `  `        ``// If y is odd,  ` `        ``// multiply x  ` `        ``// with result ` `        ``if` `(``\$y` `& 1) ` `            ``\$res` `= (``\$res` `* ``\$x``) % ``\$p``; ` ` `  `        ``// y must be  ` `        ``// even now ` `        ``// y = y/2 ` `        ``\$y` `= ``\$y` `>> 1;  ` `        ``\$x` `= (``\$x` `* ``\$x``) % ``\$p``; ` `    ``} ` `    ``return` `\$res``; ` `} ` ` `  `// Returns n^(-1) mod p ` `function` `modInverse(``\$n``, ``\$p``) ` `{ ` `    ``return` `power(``\$n``, ``\$p` `- 2, ``\$p``); ` `} ` ` `  `// Returns nCr % p using ` `// Fermat's little ` `// theorem. ` `function` `nCrModPFermat(``\$n``, ``\$r``, ``\$p``) ` `{ ` `     `  `    ``// Base case ` `    ``if` `(``\$r``==0) ` `        ``return` `1; ` ` `  `    ``// Fill factorial array so that we ` `    ``// can find all factorial of r, n ` `    ``// and n-r ` `    ``//\$fac[\$n+1]; ` `    ``\$fac`` = 1; ` `    ``for` `(``\$i` `= 1; ``\$i` `<= ``\$n``; ``\$i``++) ` `        ``\$fac``[``\$i``] = ``\$fac``[``\$i` `- 1] * ` `                        ``\$i` `% ``\$p``; ` ` `  `    ``return` `(``\$fac``[``\$n``] * modInverse(``\$fac``[``\$r``], ``\$p``) % ``\$p` `* ` `             ``modInverse(``\$fac``[``\$n` `- ``\$r``], ``\$p``) % ``\$p``) % ``\$p``; ` `} ` ` `  `    ``// Driver Code ` `    ``// p must be a prime ` `    ``// greater than n. ` `    ``\$n` `= 10; ` `    ``\$r` `= 2; ` `    ``\$p` `= 13; ` `    ``echo` `"Value of nCr % p is "``, ` `         ``nCrModPFermat(``\$n``, ``\$r``, ``\$p``); ` `         `  `// This code is contributed by Ajit. ` `?> `

Output:

```Value of nCr % p is 6
```

Improvements:
In competitive programming, we can pre-compute fac[] for given upper limit so that we don’t have to compute it for every test case. We also can use unsigned long long int everywhere to avoid overflows.