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}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Mathematics

Starter code: #User function Template for python3

class Solution:
    def ncr (self, n, r):
        #complete the function here

Solutions:
class Solution:

	def ncr(self, n, r):
		if r <= 0 or r > n:
			return 0
		mod = 1000000007
		num = 1
		den = 1
		for i in range(1, r + 1):
			num = num * n % mod
			den = den * i % mod
			n -= 1
		return num * pow(den, mod - 2, mod) % mod


MOD = int(1000000000.0 + 7)

def pow(a, b):
	if b == 0:
		return 1
	ans = 1
	m = 1
	while b:
		if b & 1:
			ans *= a
			ans %= MOD
		a *= a
		a %= MOD
		b >>= 1
	return ans

class Solution:

	def ncr(self, n, r):
		dp = [0] * (n + 1)
		dp[0] = 1
		if r > n:
			return 0
		for i in range(1, n + 1):
			dp[i] = i * dp[i - 1]
			dp[i] %= MOD
		nume = dp[n]
		deno = dp[r] * dp[n - r] % MOD
		ans = nume * pow(deno, MOD - 2)
		ans %= MOD
		return ans


class Solution:

	def ncr(self, n, r):
		if r > n:
			return 0
		m = 1000000007
		inv = [0 for i in range(r + 1)]
		inv[0] = 1
		if r + 1 >= 2:
			inv[1] = 1
		for i in range(2, r + 1):
			inv[i] = m - m // i * inv[m % i] % m
		ans = 1
		for i in range(2, r + 1):
			ans = ans % m * (inv[i] % m) % m
		for i in range(n, n - r, -1):
			ans = ans % m * (i % m) % m
		return ans


class Solution:

	def ncr(self, n, r):
		p = 10 ** 9 + 7
		(num, den) = (1, 1)
		for i in range(r):
			num = num * (n - i) % p
			den = den * (i + 1) % p
		return pow(den, p - 2, p) * num % p


class Solution:

	def ncr(self, n, r):
		p = 1000000007
		num = den = 1
		for i in range(r):
			num = num * (n - i) % p
			den = den * (i + 1) % p
		return num * pow(den, p - 2, p) % p


class Solution:

	def ncr(self, n, r):
		if r > n:
			return 0

		def power(a, b, m):
			a = a % m
			ans = 1
			while b:
				if b & 1:
					ans = ans * a % m
				a = a * a % m
				b >>= 1
			return ans
		c = [1]
		m = 10 ** 9 + 7
		for i in range(1, n + 1):
			c.append(c[i - 1] * i % m)
		k = c[n]
		k = k * power(c[r], m - 2, m) % m
		k = k * power(c[n - r], m - 2, m) % m
		return k