modular multiplicative inverse of an number for calculating nCr % 10000007 (combination)

Question

I am trying to calculate nCr % M. So what I am doing is

nCr = n!/(n-r)!*r! %M

In other words, nCr = n! * (inverseFactorial(n-r)*inverseFactorial(r)). So i am precomputing the values for factorial and inverseFactorial of numbers from range 1 to 10^5. Basically, I am trying to implement this first answer.

https://www.quora.com/How-do-I-find-the-value-of-nCr-1000000007-for-the-large-number-n-n-10-6-in-C

This is my code.

        //fill fact
        fact[0]=1;
        for(int i=1;i<100001;i++){
            fact[i]=fact[i-1]*i%1000000007;
            //fact[i]=fact[i]%1000000007;
        }

        //fill ifact - inverse of fact
        ifact[0]=1;
        for(int i=1;i<100001;i++){
            ifact[i] = ifact[i-1]*inverse(i)%1000000007;
            //ifact[i]=ifact[i]%1000000007;
        }

And the methods are

public static long fastcomb(int n,int r){

        long ans = ifact[r]*ifact[n-r];
        System.out.println(ifact[r]);
        System.out.println(ifact[n-r]);
        ans = ans%1000000007;
        ans=ans*fact[n];
        System.out.println(fact[n]);
        ans = ans%1000000007;
        return ans;

    }


 public static int modul(int x){
        x = x%1000000007;
        if(x<0){
            x+=1000000007;
        }
        return x;
    }

public static int inverse(int x){
    int mod = modul(x);
    if(mod==1){
        return 1;
    }

    return modul((-1000000007/mod)*(ifact[1000000007%mod]%1000000007));

}

I am not sure where i am going wrong? Please help what i am doing wrong as for ifact[2] it is showing me 500000004.

Answer 1

Here is the Fermat's Little theorem implementation for multiplicative inverse. I tested it and it works.

   static long modInverse(long a, long m)
   {
         return power(a, m - 2, m);
   }

   // To compute x^y under modulo m
   static long power(long x, long y, long m)
   {
      if (y == 0)
         return 1;

      long p = power(x, y / 2, m) % m;
      p = (p * p) % m;

      if (y % 2 == 0)
         return p;
      else
         return (x * p) % m;
   } 

I'm working on nCr mod M, you don't need that array to find it.

Find the following implementation of nCr mod m, please check it with your values, remember m should be a prime for this method.

   static long nCr_mod_m(long n, long r, long m)
   {
      if(n-r < r) r = (n-r);    //  since nCr = nC(n-r)

      long top_part = n, bottom_part=1;

      for(long i=1; i<r; i++)
         top_part = (top_part*(n-i)) % m;

      for(long i=2; i<=r; i++)
         bottom_part = (bottom_part * modInverse(i, m))%m;

      return (top_part*bottom_part)%m;

   }