You are standing on a point (n, m) and you want to go to origin (0, 0) by taking steps either left or up i.e. from each point you are allowed to move either in (n-1, m) or (n, m-1). Find the number of paths from point to origin.
Example 1:
Input:
N=3, M=0
Output: 1
Explanation: Path used was - 
             (3,0)  --> ( 2,0) --> (1,0) --> (0,0).
             We can see that there is no other path
             other than this path for this testcase.
 
Example 2:
Input:
N=3, M=6
Output: 84 
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function ways() that takes array N and integer M as parameters and returns the total number of paths from point(n,m) to the origin(0,0) % 1000000007.
 
Expected Time Complexity: O(N*M).
Expected Auxiliary Space: O(N*M).
Constraints:
1 ≤ N, M ≤ 500

Source: geeksforgeeks | Difficulty: EASY
Tags: Matrices

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def ways(self, n,m):

        #write you code here



Solutions:
class Solution:

	def ways(self, n, m):
		if n == 0 or m == 0:
			return 1
		dp = [[1 for i in range(m + 1)] for j in range(n + 1)]
		for ctr in range(m):
			dp[0][ctr] = 1
		for ctr in range(n):
			dp[ctr][0] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[n][m] % (10 ** 9 + 7)


class Solution:

	def ways(self, n, m):
		mod = 10 ** 9 + 7
		dp = [[0] * (m + 1) for i in range(n + 1)]
		dp[n][m] = 1
		for i in range(n, -1, -1):
			for j in range(m, -1, -1):
				if i == n and j == m:
					continue
				if i + 1 <= n:
					dp[i][j] += dp[i + 1][j]
				if j + 1 <= m:
					dp[i][j] += dp[i][j + 1]
				dp[i][j] = dp[i][j] % mod
		return dp[0][0]


h = {}

class Solution:

	def __init__(self):
		pass

	def ways(self, n, m):
		s1 = str(n) + '_' + str(m)
		if n == 0 and m == 0:
			return 1
		if n < 0 or m < 0:
			return 0
		elif h.get(s1, -1) != -1:
			return h[s1]
		h[s1] = (self.ways(n, m - 1) + self.ways(n - 1, m)) % 1000000007
		return h[s1]


import sys
sys.setrecursionlimit(10 ** 6)
h = {}

class Solution:

	def __init__(self):
		pass

	def ways(self, n, m):
		s1 = str(n) + '_' + str(m)
		if n == 0 and m == 0:
			return 1
		if n < 0 or m < 0:
			return 0
		elif h.get(s1, -1) != -1:
			return h[s1]
		h[s1] = (self.ways(n, m - 1) + self.ways(n - 1, m)) % 1000000007
		return h[s1]


class Solution:

	def ways(self, n, m):
		l = []
		for i in range(n + 1):
			l += [[-1] * (m + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0 and j == 0:
					l[i][j] = 0
				elif i == 0 or j == 0:
					l[i][j] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				l[i][j] = (l[i - 1][j] + l[i][j - 1]) % 1000000007
		return l[n][m]


import math

class Solution:

	def ways(self, n, m):
		return math.factorial(n + m) // (math.factorial(n) * math.factorial(m)) % 1000000007


class Solution:

	def ways(self, n, m):
		dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for j in range(1, m + 1):
			dp[0][j] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[n][m] % (10 ** 9 + 7)


class Solution:

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


class Solution:

	def ways(self, n, m):
		matrix = [[1] * (m + 1)]
		for _ in range(n):
			matrix.append([1])
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				matrix[i].append((matrix[i][-1] + matrix[i - 1][j]) % (10 ** 9 + 7))
		return matrix[n][m]


memo = [[-1 for j in range(501)] for i in range(501)]

class Solution:

	def ways(self, n, m):
		self.helper(n, m)
		return memo[n][m] % (10 ** 9 + 7)

	def helper(self, i, j):
		if i < 0 or j < 0:
			return 0
		if i == 0 and j == 0:
			return 1
		if memo[i][j] != -1:
			return memo[i][j]
		else:
			memo[i][j] = self.helper(i - 1, j) + self.helper(i, j - 1)
			return memo[i][j]


class Solution:

	def ways(self, n, m):
		mod = 1000000007
		dp = [[0 for x in range(m + 1)] for y in range(n + 1)]
		for i in range(m + 1):
			dp[n][i] = 1
		for i in range(n + 1):
			dp[i][m] = 1
		for step in range(m + 1, -1, -1):
			i = n
			j = step
			while j <= m and i >= 0:
				if i != n and j != m:
					dp[i][j] = (dp[i + 1][j] + dp[i][j + 1]) % mod
				j += 1
				i -= 1
		k = n - 1
		while k >= 0:
			i = k
			j = 0
			while j <= m and i >= 0:
				if i != n and j != m:
					dp[i][j] = (dp[i + 1][j] + dp[i][j + 1]) % mod
				j += 1
				i -= 1
			k -= 1
		return dp[0][0]


class Solution:

	def ways(self, n, m):
		a = [1] * (m + 1)
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				a[j] = (a[j] + a[j - 1]) % 1000000007
		return a[m]


class Solution:

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

		def w(n, m):
			if n < 0 or m < 0:
				return 0
			if n == 0 and m == 0:
				return 1
			if (n, m) in dp:
				return dp[n, m]
			dp[n, m] = (w(n - 1, m) + w(n, m - 1)) % 1000000007
			return dp[n, m]
		return w(n, m)


class Solution:

	def ways(self, n, m):
		mod = 10 ** 9 + 7
		t = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(0, n + 1):
			t[i][0] = 1
		for j in range(0, m + 1):
			t[0][j] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				t[i][j] = t[i - 1][j] + t[i][j - 1]
		return t[n][m] % mod


class Solution:

	def ways(self, n, m):
		bncoff = n + m
		k = n
		tri = [0] * (k + 1)
		tri[0] = 1
		for i in range(1, bncoff + 1):
			j = min(i, k)
			while j > 0:
				tri[j] = tri[j] + tri[j - 1]
				j -= 1
		return tri[k] % 1000000007


import math

class Solution:

	def ways(self, n, m):
		return math.factorial(n + m) // (math.factorial(m) * math.factorial(n)) % (10 ** 9 + 7)
t = int(input())
for _ in range(0, t):
	(x, y) = list(map(int, input().split()))
	ob = Solution()
	print(ob.ways(x, y))


class Solution:

	def ways(self, n, m):
		data = [[0 for i in range(n + 1)] for i in range(m + 1)]
		for i in range(m + 1):
			for j in range(n + 1):
				if i == 0 or j == 0:
					data[i][j] = 1
				else:
					data[i][j] = data[i - 1][j] + data[i][j - 1]
		return data[m][n] % 1000000007


class Solution:

	def ways(self, n, m):
		dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if i == 0:
					dp[i][j] = 1
				elif j == 0:
					dp[i][j] = 1
				elif i == 0 and j == 0:
					dp[i][j] = 1
				else:
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[n][m] % 1000000007
		memo = {}

		def helper(r, c):
			if (r, c) in memo:
				return memo[r, c]
			if r < 0 or c < 0:
				return 0
			if r == 0 and c == 0:
				return 1
			pick = helper(r - 1, c)
			notpick = helper(r, c - 1)
			memo[r, c] = pick + notpick
			return memo[r, c]
		return helper(n, m) % 1000000007


class Solution:

	def ways(self, n, m):
		l = []
		for i in range(n):
			l += [[1 for j in range(m)]]
		if n == 0 or m == 0:
			return 1
		for i in range(n):
			for j in range(m):
				if i == 0 and j == 0:
					l[i][j] += 1
				elif i == 0:
					l[i][j] = l[i][j - 1] + 1
				elif j == 0:
					l[i][j] = l[i - 1][j] + 1
				else:
					l[i][j] = l[i - 1][j] + l[i][j - 1]
		return l[-1][-1] % (10 ** 9 + 7)


mod = 10 ** 9 + 7

def calculate():
	dp = []
	for i in range(0, 501):
		dp.append([0] * 501)
	for i in range(0, 501):
		dp[0][i] = 1
		dp[i][0] = 1
	dp[0][0] = 1
	for i in range(1, 501):
		for j in range(1, 501):
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
	return dp
dp = calculate()

class Solution:

	def ways(self, x, y):
		return dp[x][y]


class Solution:

	def ways(self, n, m):
		a = n + m
		k = min(n, m)
		dp = [0] * (k + 1)
		dp[0] = 1
		for i in range(1, a + 1):
			j = min(i, k)
			while j > 0:
				dp[j] = dp[j] + dp[j - 1]
				j -= 1
		return dp[k] % 1000000007


class Solution:

	def ways(self, n, m):
		if m == 0 or n == 0:
			return 1
		dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
		MOD = 10 ** 9 + 7
		dp[0][0] = 1
		for i in range(n + 1):
			dp[i][0] = 1
		for j in range(m + 1):
			dp[0][j] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				dp[i][j] = int((dp[i - 1][j] + dp[i][j - 1]) % MOD)
		return dp[n][m]


class Solution:

	def ways(self, n, m):
		if n == 0 or m == 0:
			return 1
		mat = [[1 for _ in range(n + 1)] for _ in range(m + 1)]
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				mat[i][j] = mat[i - 1][j] + mat[i][j - 1]
		return mat[-1][-1] % 1000000007