@@ -0,0 +1,1531 @@
+package com.williamfiset.algorithms.math;%0A%0Aimport java.math.BigInteger;%0A%0Apublic class NChooseRModPrime %7B%0A  /**%0A   * Calculate the value of C(N, R) %25 P using Fermat's Little Theorem.%0A   *%0A   * @param N%0A   * @param R%0A   * @param P%0A   * @return The value of N choose R Modulus P%0A   */%0A  public static long compute(int N, int R, int P) %7B%0A    if (R == 0) return 1;%0A%0A    long%5B%5D factorial = new long%5BN + 1%5D;%0A    factorial%5B0%5D = 1;%0A%0A    for (int i = 1; i %3C= N; i++) %7B%0A      factorial%5Bi%5D = factorial%5Bi - 1%5D * i %25 P;%0A    %7D%0A%0A    return (factorial%5BN%5D%0A            * ModularInverse.modInv(factorial%5BR%5D, P)%0A            %25 P%0A            * ModularInverse.modInv(factorial%5BN - R%5D, P)%0A            %25 P)%0A        %25 P;%0A  %7D%0A%0A  private static String bigIntegerNChooseRModP(int N, int R, int P) %7B%0A    if (R == 0) return %221%22;%0A    BigInteger num = new BigInteger(%221%22);%0A    BigInteger den = new BigInteger(%221%22);%0A    while (R %3E 0) %7B%0A      num = num.multiply(new BigInteger(%22%22 + N));%0A      den = den.multiply(new BigInteger(%22%22 + R));%0A      BigInteger gcd = num.gcd(den);%0A      num = num.divide(gcd);%0A      den = den.divide(gcd);%0A      N--;%0A      R--;%0A    %7D%0A    num = num.divide(den);%0A    num = num.mod(new BigInteger(%22%22 + P));%0A    return num.toString();%0A  %7D%0A%0A  public static void main(String args%5B%5D) %7B%0A    int N = 500;%0A    int R = 250;%0A    int P = 1000000007;%0A    int expected = Integer.parseInt(bigIntegerNChooseRModP(N, R, P));%0A    long actual = compute(N, R, P);%0A    System.out.println(expected); // 515561345%0A    System.out.println(actual); // 515561345%0A  %7D%0A%7D%0A

Add N choose R mod prime