nCr = (n-r+1)*(n-r+2)*….*n / (r!)

Create an array arr of numbers from n-r+1 to n which will be of size r. As nCr is always an integer, all numbers in the denominator should cancel with the product of numerator (represented by arr).

for i = 1 to i = r,

search arr, if arr[j] and i have gcd>1, divide both by the gcd and when i becomes 1, stop the search

Now, the answer is just the product of arr, whose value mod 10^9+7 can be found using a singe pass and the formula use (a*b)%mod = (a%mod * b%mod)%mod

- Java
- Python3

`import`

`java.util.*;`

`class`

`GFG`

`{`

` `

`static`

`int`

`gcd(`

`int`

`a, `

`int`

`b) `

`// function to find gcd of two numbers in O(log(min(a,b)))`

` `

`{`

` `

`if`

`(b==`

`0`

`) `

`return`

`a;`

` `

`return`

`gcd(b,a%b);`

` `

`}`

` `

`static`

`int`

`nCr(`

`int`

`n, `

`int`

`r)`

` `

`{`

` `

`if`

`(r>n) `

`// base case`

` `

`return`

`0`

`;`

` `

`if`

`(r>n-r) `

`// C(n,r) = C(n,n-r) better time complexity for lesser r value`

` `

`r = n-r;`

` `

`int`

`mod = `

`1000000007`

`;`

` `

`int`

`[] arr = `

`new`

`int`

`[r]; `

`// array of elements from n-r+1 to n`

` `

`for`

`(`

`int`

`i=n-r+`

`1`

`; i<=n; i++)`

` `

`{`

` `

`arr[i+r-n-`

`1`

`] = i;`

` `

`}`

` `

`long`

`ans = `

`1`

`;`

` `

`for`

`(`

`int`

`k=`

`1`

`;k<r+`

`1`

`;k++) `

`// for numbers from 1 to r find arr[j] such that gcd(i,arr[j])>1`

` `

`{`

` `

`int`

`j=`

`0`

`, i=k;`

` `

`while`

`(j<arr.length)`

` `

`{`

` `

`int`

`x = gcd(i,arr[j]);`

` `

`if`

`(x>`

`1`

`)`

` `

`{`

` `

`arr[j] /= x; `

`// if gcd>1, divide both by gcd`

` `

`i /= x;`

` `

`}`

` `

`if`

`(i==`

`1`

`)`

` `

`break`

`; `

`// if i becomes 1, no need to search arr`

` `

`j += `

`1`

`;`

` `

`}`

` `

`}`

` `

`for`

`(`

`int`

`i : arr) `

`// single pass to multiply the numerator`

` `

`ans = (ans*i)%mod;`

` `

`return`

`(`

`int`

`)ans;`

` `

`}`

` `

`// Driver code`

` `

`public`

`static`

`void`

`main(String[] args)`

` `

`{`

` `

`int`

`n = `

`5`

`, r = `

`2`

`;`

` `

`System.out.print(`

`"Value of C("`

`+ n+ `

`", "`

`+ r+ `

`") is "`

` `

`+nCr(n, r) +`

`"\n"`

`);`

` `

`}`

`}`

`// This code is contributed by Gautam Wadhwani`

**Output**

Value of C(5, 2) is 10

**Time Complexity:** O(( min(r, n-r)^2 ) * log(n)), **useful when n >> r or n >> (n-r)**

**Auxiliary Space:** O(min(r, n-r))