Find ^{n}C_{r} for given n and r.
As answer can be very large, compute it modulo 10^{9} + 7.
Example 1:
Input: n = 3, r = 2
Output: 3
Explanation: ^{3}C_{2} = 3
​Example 2:
Input: n = 4, r = 2
Output: 6
Explanation: ^{4}C_{2} = 6
Your Task:
You don't need to read input or print anything. Your task is to complete the function ncr() which takes n and r as inputs and returns the answer modulo 10^{9} + 7.
Expected Time Complexity: O(n * log n)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ r, n ≤ 10^{5}

见题面

见题面