nCrModPFermat

Fermat's little theorem states that if p is a prime number, then for any integer a, the number a p – a is an integer multiple of p. ap ≡ a (mod p). Special Case: If a is not divisible by p, Fermat's little theorem is equivalent to the statement that a p-1-1 is an integer multiple of p. Here a is not divisible by p. We will use this theorem to find nCr.

function nCrModPFermat(n, r, p)
{
    //Logic
    if (r == 0) return 1;
  var fac = new Array(n + 1).fill(1);
  fac[0] = 1;
  for(var i = 1; i <= n; i++) fac[i] = fac[i-1] * i % p;
  //Refer to inverse_mod_q Post to get details of the function
  return (fac[n] * inverse_mod_q(fac[r], p) % p * inverse_mod_q(fac[n - r], p) % p) % p;
}