Given two integers n and r, find ^{n}C_{r. }Since the answer may be very large, calculate the answer modulo 10^{9}+7.
Example 1:
Input: n = 3, r = 2
Output: 3
Explaination: ^{3}C_{2} = 3. 
Example 2:
Input: n = 2, r = 4
Output: 0
Explaination: r is greater than n.
Your Task:
You do not need to take input or print anything. Your task is to complete the function nCr() which takes n and r as input parameters and returns ^{n}C_{r }modulo 10^{9}+7..
Expected Time Complexity: O(n*r)
Expected Auxiliary Space: O(r)
Constraints:
1 ≤ n ≤ 1000
1 ≤ r ≤ 800

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Mathematics

Starter code: #User function Template for python3



class Solution:

    def nCr(self, n, r):

        # code here

Solutions:
class Solution:

	def nCr(self, n, r):
		d = [1]
		for i in range(1, n + 1):
			d.append(d[i - 1] * i)
		try:
			return d[n] // (d[r] * d[n - r]) % 1000000007
		except:
			return 0


import math

class Solution:

	def nCr(self, n, r):
		if n > r:
			return math.factorial(n) // (math.factorial(r) * math.factorial(n - r)) % (10 ** 9 + 7)
		return 0


class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		r = min(r, n - 1)
		table = [0 for _ in range(r + 1)]
		table[0] = 1
		j = 1
		while j < n + 1:
			for i in range(r, 0, -1):
				table[i] = (table[i - 1] + table[i]) % 1000000007
			j += 1
		return table[r]


class Solution:

	def nCr(self, n, r):
		dp = [[0 for j in range(r + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		if r > n:
			return 0
		if r == n:
			return 1
		for i in range(1, n + 1):
			for j in range(1, min(i + 1, r + 1)):
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % (10 ** 9 + 7)
		return dp[n][r]


class Solution:

	def nCr(self, n, r):
		memo = {}

		def recurse(n, r):
			if n == r:
				return 1
			if r > n:
				return 0
			if r == 0:
				return 1
			key = str(n) + ',' + str(r)
			if memo.get(key, -1) != -1:
				return memo[key]
			memo[key] = recurse(n - 1, r - 1) + recurse(n - 1, r)
			return memo[key] % (10 ** 9 + 7)
		return recurse(n, r)


import math

class Solution:

	def nCr(self, n, r):
		mod = 10 ** 9 + 7
		a = math.factorial(n)
		b = math.factorial(r)
		if n > r:
			c = math.factorial(n - r)
			return a // (b * c) % mod
		return 0


class Solution:

	def getFactorial(self, n):
		if n == 1:
			return 1
		return n * self.getFactorial(n - 1)

	def getNumber(self, n, r):
		c = n
		for i in range(1, r):
			n *= c - i
		return n

	def nCr(self, n, r):
		mod = 10 ** 9 + 7
		if r > n:
			return 0
		d = self.getFactorial(r)
		n = self.getNumber(n, r)
		return n // d % mod


import math

class Solution:

	def nCr(self, n, r):
		mod = 1000000000 + 7
		a = math.factorial(n)
		b = math.factorial(r)
		if n == r:
			return 1
		elif n > r:
			c = math.factorial(n - r)
			return a // (b * c) % mod
		else:
			return 0


class Solution:

	def getfact(self, n):
		if n == 1:
			return 1
		return n * self.getfact(n - 1)

	def getnum(self, n, r):
		k = n
		for i in range(1, r):
			n *= k - i
		return n

	def nCr(self, n, r):
		if r > n:
			return 0
		deno = self.getfact(r)
		numo = self.getnum(n, r)
		k = 1000000007
		return numo // deno % k


import math

class Solution:

	def nCr(self, n, r):
		mod = 10 ** 9 + 7
		y = math.factorial(n)
		x = math.factorial(r)
		if n > r:
			z = math.factorial(n - r)
			return y // (x * z) % mod
		return 0


class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		dp = {}

		def fact(n):
			if n == 0 or n == 1:
				return 1
			if n in dp:
				return dp[n]
			dp[n] = n * fact(n - 1)
			return dp[n]
		return fact(n) // (fact(r) * fact(n - r)) % (10 ** 9 + 7)


class Solution:

	def fun(self, n, r, dp):
		if n == 0 or r == 0:
			if r:
				return 0
			else:
				return 1
		if dp[n][r] != -1:
			return dp[n][r]
		dp[n][r] = (self.fun(n - 1, r - 1, dp) + self.fun(n - 1, r, dp)) % 1000000007
		return dp[n][r]

	def nCr(self, n, r):
		dp = []
		for i in range(n + 1):
			t = [-1] * (r + 1)
			dp.append(t)
		if r == n:
			return 1
		elif r > n:
			return 0
		return self.fun(n, r, dp)


class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		j = r
		(new, old) = (1, 1)
		for i in range(j):
			new = new * n
			old = old * r
			n = n - 1
			r = r - 1
		ans = new // old
		return ans % (10 ** 9 + 7)


class Solution:

	def solution(self, n, k, dp):
		if k > n:
			return 0
		if k == 0 or k == n:
			return 1
		if dp[n][k] != -1:
			return dp[n][k]
		dp[n][k] = self.solution(n - 1, k - 1, dp) + self.solution(n - 1, k, dp)
		return dp[n][k] % (10 ** 9 + 7)

	def nCr(self, n, r):
		dp = [[0] * (r + 1) for row in range(n + 1)]
		if r > n:
			return 0
		if r == 0 or r == n:
			return 1
		for i in range(0, n + 1):
			for j in range(0, r + 1):
				if i == j or j == 0:
					dp[i][j] = 1
				else:
					dp[i][j] = dp[i - 1][j - 1] % (10 ** 9 + 7) + dp[i - 1][j] % (10 ** 9 + 7)
		return dp[n][r] % (10 ** 9 + 7)


def ftrl(x):
	if x == 0:
		return 1
	elif x == 1:
		return 1
	else:
		return x * ftrl(x - 1)

class Solution:

	def nCr(self, n, r):
		l = 1000000007
		if n < r:
			return 0
		nu = ftrl(n)
		d1 = ftrl(n - r)
		d2 = ftrl(r)
		return nu // (d1 * d2) % l


class Solution:

	def nCr(self, n, r):
		rem = 1000000007
		if r > n:
			return 0
		else:
			r = factorial(n) // (factorial(r) * factorial(n - r))
			return r % rem
from math import factorial


class Solution:

	def nCr(self, n, r):
		if n <= r:
			return 0

		def fun(n):
			dp = [-1] * (n + 1)
			dp[0] = 0
			dp[1] = 1
			for i in range(2, n + 1):
				dp[i] = dp[i - 1] * i
			return dp[n]
		factN = fun(n)
		factR = fun(r)
		fact = fun(n - r)
		return factN // (factR * fact) % (10 ** 9 + 7)


import math

class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		n1 = math.factorial(n)
		r1 = math.factorial(r)
		d = math.factorial(n - r)
		ans = n1 // (r1 * d)
		return ans % 1000000007


import math

class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		l = math.factorial(n)
		t = math.factorial(r)
		k = math.factorial(n - r)
		ans = l // (t * k)
		return ans % 1000000007


def getfact(n):
	if n == 1:
		return 1
	return n * getfact(n - 1)

def getnum(n, r):
	k = n
	for i in range(1, r):
		n *= k - i
	return n

class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		denominator = getfact(r)
		numerator = getnum(n, r)
		k = 10 ** 9 + 7
		return numerator // denominator % k


class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		MOD = int(1000000000.0) + 7
		dp = [[0] * (r + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(min(i, r) + 1):
				if j == 0 or j == i:
					dp[i][j] = 1
				else:
					dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD
		return dp[n][r]


class Solution:

	def factorial(self, n):
		if n == 0:
			return 1
		else:
			return n * self.factorial(n - 1)

	def nCr(self, n, r):
		if n < r:
			return 0
		else:
			cal = self.factorial(n) // (self.factorial(n - r) * self.factorial(r))
			return cal % (10 ** 9 + 7)


import math

class Solution:

	def nCr(self, n, r):
		mod = 10 ** 9 + 7
		A = math.factorial(n)
		B = math.factorial(r)
		if n > r:
			C = math.factorial(n - r)
			return A // (B * C) % mod
		return 0


class Solution:

	def nCr(self, n, r):

		def factorial(x):
			fact = 1
			for i in range(1, x + 1):
				fact = fact * i
			return fact
		op = 1
		n_fact = factorial(n)
		r_fact = factorial(r)
		x = n - r
		n_minus_r_fact = factorial(x)
		op = int(n_fact // (r_fact * n_minus_r_fact) % (10 ** 9 + 7))
		return op


class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		p = 1
		q = 1
		s = 1
		for i in range(1, n + 1):
			p = p * i
			if i == r:
				q = p
			if i == n - r:
				s = p
		return p // (q * s) % 1000000007


class Solution:

	def nCr(self, n, r):
		mod = int(1000000000.0) + 7
		if r > n:
			return 0
		if r == 0 or r == n:
			return 1
		dp = [[0 for j in range(r + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, r + 1):
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod
		return dp[n][r]


class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		if n - r < r:
			r = n - r
		c = 1
		for i in range(r):
			c = c * (n - i) // (i + 1)
		return c % (10 ** 9 + 7)


class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		um = 1
		lm = 1
		nr = n - r
		if nr < r:
			for i in range(nr):
				um *= n
				n -= 1
			N = nr
			while N:
				lm *= N
				N -= 1
			return um // lm % 1000000007
		for i in range(r):
			um *= n
			n -= 1
		N = r
		while N:
			lm *= N
			N -= 1
		return um // lm % 1000000007


import math

class Solution:

	def nCr(self, n, r):
		if n < r:
			return 0
		mod = 10 ** 9 + 7
		N = math.factorial(n)
		R = math.factorial(r)
		Res = N // (R * math.factorial(n - r))
		Res = Res % mod
		return Res


class Solution:

	def nCr(self, n, r):
		mod = 10 ** 9 + 7
		if r > n:
			return 0
		if r == n or r == 0:
			return 1
		nc = [1]
		for i in range(1, r + 1):
			x = nc[i - 1] * (n - i + 1) // i
			nc.append(x)
		return nc[-1] % mod


def fact(x):
	f = 1
	for i in range(1, x + 1):
		f = f * i
	return f

class Solution:

	def nCr(self, n, r):
		comb = fact(n) // (fact(r) * fact(n - r))
		ans = comb % (10 ** 9 + 7)
		return ans


import math

class Solution:

	def nCr(self, n, r):
		ans = int(math.factorial(n) // (math.factorial(r) * math.factorial(abs(n - r))))
		result = ans % (10 ** 9 + 7)
		return int(result)


class Solution:

	def nCr(self, n, r):

		def fact(num):
			if num == 1:
				return 1
			return num * fact(num - 1)
		if r > n:
			return 0
		ans = fact(n) // (fact(r) * fact(n - r))
		return ans % (10 ** 9 + 7)


from functools import lru_cache

class Solution:

	def nCr(self, n, r):
		MOD = 10 ** 9 + 7
		dp = {}

		def solve(n):
			if n <= 1:
				return 1
			if n in dp:
				return dp[n]
			else:
				ans = n * solve(n - 1)
			dp[n] = ans
			return ans
		c1 = solve(n)
		c2 = solve(r)
		c3 = solve(n - r)
		return c1 // (c2 * c3) % MOD


class Solution:

	def nCr(self, n, r):
		import math
		m = 1000000007
		if r > n:
			return 0
		else:
			x = math.factorial(n)
			y = math.factorial(r)
			z = math.factorial(n - r)
			return int(x // (y * z)) % m


class Solution:

	def nCr(self, n, r):
		dp = [[0 for j in range(r + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for j in range(1, r + 1):
			dp[0][j] = 0
		for i in range(1, n + 1):
			for j in range(1, r + 1):
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
		return dp[n][r] % 1000000007


class Solution:

	def nCr(self, n, r):
		c = 1
		a = 1
		b = 1
		x = 10 ** 9 + 7
		if n > r:
			for i in range(2, n + 1):
				c = c * i
			for j in range(2, n - r + 1):
				a = a * j
			for k in range(2, r + 1):
				b = b * k
			return int(c // (b * a) % x)
		else:
			return 0


import math

class Solution:

	def nCr(self, n, r):
		if n > r:
			res = math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
			return res % (1000000000 + 7)
		return 0


class Solution:

	def nCr(self, n, r):
		fac = 1
		if n < r:
			return 0
		facr = 0
		facnr = 0
		for i in range(1, n + 1):
			fac = fac * i
			if i == r:
				facr = fac
			if i == n - r:
				facnr = fac
		return fac // (facr * facnr) % (10 ** 9 + 7)


class Solution:

	def nCr(self, n, r):
		dp = []
		dp.append(1)
		for i in range(1, r + 1):
			dp.append((n - i + 1) * dp[i - 1] // i)
		return dp[r] % 1000000007


class Solution:

	def nCr(self, n, r):

		def fact(n):
			A = 1
			if n == 0:
				return A
			else:
				return fact(n - 1) * n
		if r > n:
			return 0
		else:
			X = fact(n) // (fact(r) * fact(n - r))
			return X % (10 ** 9 + 7)


class Solution:

	def nCr(self, n, r):
		res = 1
		for i in range(1, r + 1):
			res = res * (n - r + i) // i
		return res % 1000000007


import math

class Solution:

	def nCr(self, n, r):
		if r <= n:
			num1 = math.factorial(n)
			den1 = math.factorial(n - r) * math.factorial(r)
			return num1 // den1 % 1000000007
		else:
			return 0


import math

class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		else:
			c = math.factorial(n)
			d = math.factorial(n - r)
			e = math.factorial(r)
			k = 1000000007
			return c // (d * e) % k


class Solution:

	def nCr(self, n, r):
		stateMap = [[0 for _ in range(n + 1)] for i in range(r + 1)]
		stateMap[0][0] = 1
		for j in range(n + 1):
			stateMap[0][j] = 1
		for c in range(1, n + 1):
			for r in range(1, r + 1):
				stateMap[r][c] = stateMap[r - 1][c - 1] + stateMap[r][c - 1]
		return stateMap[r][n] % (10 ** 9 + 7)


class Solution:

	def nCr(self, n, r):
		t = [[0] * (r + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(r + 1):
				if j == 0 or i == j:
					t[i][j] = 1
				elif j == 1:
					t[i][j] = i
				else:
					t[i][j] = (t[i - 1][j] + t[i - 1][j - 1]) % (10 ** 9 + 7)
		return t[-1][-1]


import math

class Solution:

	def nCr(self, n, r):
		ans = math.factorial(n) // (math.factorial(r) * math.factorial(abs(n - r)))
		return ans % (pow(10, 9) + 7)


class Solution:

	def nCr(self, n, r):
		if n < r:
			return 0
		else:
			return Solution.nPr(self, n, r) // Solution.factorial(self, r) % (7 + 10 ** 9)

	def nPr(self, n, r):
		return Solution.factorial(self, n) // Solution.factorial(self, n - r)

	def factorial(self, N):
		if N == 0:
			return 1
		else:
			return N * Solution.factorial(self, N - 1)


import math

class Solution:

	def nCr(self, n, r):
		mod = 1000000007
		fact = [0] * (r + 1)
		fact[0] = 1
		for i in range(1, n + 1):
			j = min(i, r)
			while j > 0:
				fact[j] = (fact[j] + fact[j - 1]) % mod
				j -= 1
		return fact[r]


class Solution:

	def factorial(self, A):
		if A == 0 or A == 1:
			return 1
		if A > 1:
			fact = 1
			for i in range(1, A + 1):
				fact = fact * i
			return fact

	def nCr(self, n, r):
		if r > n:
			return 0
		else:
			return self.factorial(n) // (self.factorial(n - r) * self.factorial(r)) % 1000000007


class Solution:

	def fac(self, n):
		if n <= 1:
			return 1
		else:
			return n * self.fac(n - 1)

	def nCr(self, n, r):
		if r > n:
			return 0
		nf = self.fac(n)
		rf = self.fac(r)
		nrf = self.fac(n - r)
		return nf // (rf * nrf) % 1000000007


import math as m

class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		if r == n:
			return 1
		else:
			prd = 1
			for i in range(r):
				prd = prd * n
				n -= 1
			w = prd // m.factorial(r)
			return w % (10 ** 9 + 7)


class Solution:

	def ncr(self, n, r):
		if n < r:
			return 0
		if r == 0 or r == n:
			return 1
		if n == 1 or n == 0:
			return 1
		if dp[n][r] != -1:
			return dp[n][r]
		ans = (self.ncr(n - 1, r) % (1000000000.0 + 7) + self.ncr(n - 1, r - 1) % (1000000000.0 + 7)) % (1000000000.0 + 7)
		dp[n][r] = int(ans)
		return dp[n][r]

	def nCr(self, n, r):
		global dp
		dp = [[-1 for i in range(r + 1)] for j in range(n + 1)]
		return self.ncr(n, r)


import numpy as np

class Solution:

	def getfact(self, n):
		if n == 1:
			return 1
		return n * self.getfact(n - 1)

	def getnum(self, n, r):
		k = n
		for i in range(1, r):
			n *= k - i
		return n

	def nCr(self, n, r):
		if r > n:
			return 0
		deno = self.getfact(r)
		numo = self.getnum(n, r)
		k = 1000000007
		return numo // deno % k


class Solution:

	def fact(self, a):
		f = 1
		for i in range(1, a + 1):
			f = f * i
		return f

	def nCr(self, n, r):
		return self.fact(n) // (self.fact(r) * self.fact(n - r)) % (10 ** 9 + 7)


class Solution:

	def nCr(self, n, r):
		if r > n:
			return 0
		else:
			(factn, factr, factc) = (1, 1, 1)
			if n == 0:
				factn = 1
			else:
				for i in range(2, n + 1):
					factn = factn * i
			if r == 0:
				factr = 1
			else:
				for i in range(2, r + 1):
					factr = factr * i
			c = n - r
			if n == 0:
				factc = 1
			else:
				for i in range(2, c + 1):
					factc = factc * i
			C = factn // (factr * factc)
			new = C % (10 ** 9 + 7)
			return new


class Solution:

	def nCr(self, n, r):
		A = n
		B = r
		C = 10 ** 9 + 7
		dp = [[0 for i in range(B + 1)] for j in range(A + 1)]
		for i in range(A + 1):
			for j in range(min(i, B) + 1):
				if j == i or j == 0:
					dp[i][j] = 1
				else:
					dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % C
		return dp[A][B] % C


class Solution:

	def Factorial(self, x):
		if x == 1:
			return 1
		Fact = x * self.Factorial(x - 1)
		return Fact

	def nCr(self, n, r):
		if r > n:
			return 0
		a = self.Factorial(n)
		b = self.Factorial(n - r)
		c = self.Factorial(r)
		return a // (b * c) % 1000000007