You are given a matrix having n rows and m columns. The special property of this matrix is that some of the cells of this matrix are given as input, which are blocked i.e. they cannot be reached. Now you have to start from the cell (1,1) and reach the end (n,m) provided during the journey you can move horizontally right from the current cell or vertically down from the current cell. Can you answer the number of ways you can traverse the matrix obeying the above constraints starting from (1,1) and ending at (n,m).
 
Example 1:
Input: n = 3, m = 3, k = 2,
blocked_cells = {{1,2},{3,2}}.
Output: 1
Explanation: There is only one path from
(1,1) to(3,3) which is (1,1)->(2,1)->(2,2)->
(2,3)->(3,3).
Example 2:
Input: n = 5, m = 5, k = 1,
blocked_cells = {{5,5}}
Output: 0
Explanation: There is no path to reach at 
(5,5) beacuse (5,5) is blocked.
 
Your Task:
You don't need to read or print anything, Your task is to complete the function FindWays() which takes n, m and blocked_cells as input parameter and returns total number of ways to reach at (n, m) modulo 10^{9} + 7.
 
Expected Time Complexity: O(n*m)
Expected Space Complexity: O(n*m)
 
Constraints:
1 <= n, m <= 500
1 <= k <= n*m

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def FindWays(self, n, m, blocked_cells):

		# Code here

Solutions:
class Solution:

	def FindWays(self, n, m, blocked_cells):
		grid = [[1] * m for _ in range(n)]
		for (i, j) in blocked_cells:
			grid[i - 1][j - 1] = 0
		for i in range(1, n):
			grid[i][0] &= grid[i - 1][0]
		for j in range(1, m):
			grid[0][j] &= grid[0][j - 1]
		for i in range(1, n):
			for j in range(1, m):
				if grid[i][j]:
					grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
		return grid[n - 1][m - 1] % (10 ** 9 + 7)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		d = [[0 for _ in range(m)] for g in range(n)]
		d[0][0] = 1
		for (h, g) in blocked_cells:
			if h == 1 and g == 1:
				return 0
			if h == n and g == m:
				return 0
			d[h - 1][g - 1] = -1
		for h in range(1, m):
			if d[0][h] == -1:
				for p in range(h + 1, m):
					d[0][p] = -1
				break
			d[0][h] = 1
		for g in range(1, n):
			if d[g][0] == -1:
				for p in range(g + 1, n):
					d[p][0] = -1
				break
			d[g][0] = 1
		for h in range(1, n):
			for g in range(1, m):
				if d[h][g] == -1:
					continue
				else:
					if d[h - 1][g] != -1:
						d[h][g] += d[h - 1][g]
					if d[h][g - 1] != -1:
						d[h][g] += d[h][g - 1]
		r = d[n - 1][m - 1]
		if r == -1:
			return 0
		return r % (10 ** 9 + 7)


from collections import defaultdict

class Solution:
	MOD = 10 ** 9 + 7

	def FindWays(self, n, m, blocked_cells):
		if [1, 1] in blocked_cells:
			return 0
		dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if [i, j] == [1, 1]:
					dp[i][j] = 1
				elif [i, j] in blocked_cells:
					dp[i][j] = 0
				else:
					dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % self.MOD
		return dp[n][m]


from collections import defaultdict

class Solution:
	dp = {}
	MOD = 10 ** 9 + 7

	def recursion(self, r, c, blocked_cells):
		if r < 1 or c < 1 or [r, c] in blocked_cells:
			return 0
		if r == 1 and c == 1:
			return 1
		if self.dp[r][c] == -1:
			self.dp[r][c] = (self.recursion(r - 1, c, blocked_cells) + self.recursion(r, c - 1, blocked_cells)) % self.MOD
		return self.dp[r][c]

	def FindWays(self, n, m, blocked_cells):
		self.dp = defaultdict(lambda : defaultdict(lambda : -1))
		return self.recursion(n, m, blocked_cells)


class Solution:

	def util(self, a, n, m, i, j):
		global dp
		if i >= n or i < 0 or j >= m or (j < 0) or (a[i][j] == 1):
			return 0
		if i == n - 1 and j == m - 1:
			return 1
		if dp[i][j] != -1:
			return dp[i][j]
		dp[i][j] = int((self.util(a, n, m, i + 1, j) % (1000000000.0 + 7) + self.util(a, n, m, i, j + 1) % (1000000000.0 + 7)) % (1000000000.0 + 7))
		return dp[i][j]

	def FindWays(self, n, m, blocked_cells):
		global dp
		a = [[0 for i in range(m)] for j in range(n)]
		dp = [[-1 for i in range(m)] for j in range(n)]
		for i in range(len(blocked_cells)):
			a[blocked_cells[i][0] - 1][blocked_cells[i][1] - 1] = 1
		return self.util(a, n, m, 0, 0)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		mod = 1000000000.0 + 7
		matrix = [[0 for i in range(m)] for j in range(n)]
		for li in blocked_cells:
			matrix[li[0] - 1][li[1] - 1] = -1
		if matrix[n - 1][m - 1] == -1:
			return 0
		prev = [0 for i in range(m)]
		for i in range(n):
			curr = [0 for i in range(m)]
			for j in range(m):
				if matrix[i][j] == -1:
					curr[j] = 0
				elif i == 0 and j == 0:
					curr[j] = 1
				else:
					up = prev[j]
					left = curr[j - 1]
					curr[j] = int((up + left) % mod)
			prev = curr
		return prev[m - 1]


class Solution:

	def FindWays(self, n, m, blocked_cells):
		mod = int(1000000000.0 + 7)
		dp = [[0 for i in range(m)] for j in range(n)]
		dp[0][0] = 1
		for i in blocked_cells:
			dp[i[0] - 1][i[1] - 1] = -1
		if dp[0][0] == -1 or dp[n - 1][m - 1] == -1:
			return 0
		for i in range(1, m):
			if dp[0][i] != -1:
				dp[0][i] = dp[0][i - 1] if dp[0][i - 1] != -1 else 0
		for j in range(1, n):
			if dp[j][0] != -1:
				dp[j][0] = dp[j - 1][0] if dp[j - 1][0] != -1 else 0
		for i in range(1, n):
			for j in range(1, m):
				if dp[i][j] != -1:
					dp[i][j] = dp[i - 1][j] if dp[i - 1][j] != -1 else 0
					dp[i][j] += dp[i][j - 1] if dp[i][j - 1] != -1 else 0
					dp[i][j] = dp[i][j] % mod
		return dp[n - 1][m - 1]


class Solution:

	def FindWays(self, n, m, blocked_cells):
		ss = set()
		for (i, j) in blocked_cells:
			ss.add((i - 1, j - 1))

		def func(i, j, n, m, ss, dp):
			if i >= n or j > m:
				return 0
			if i == n - 1 and j == m - 1:
				return 1
			if (i, j) in ss:
				return 0
			if dp[i][j] != 0:
				return dp[i][j]
			right = func(i, j + 1, n, m, ss, dp)
			down = func(i + 1, j, n, m, ss, dp)
			dp[i][j] = right + down
			return dp[i][j]
		if (n - 1, m - 1) in ss:
			return 0
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		kk = func(0, 0, n, m, ss, dp)
		return kk % (10 ** 9 + 7)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		(m, n) = (n, m)
		dp = [[0] * n for i in range(m)]
		matrix = [[0] * n for i in range(m)]
		for i in range(len(blocked_cells)):
			matrix[blocked_cells[i][0] - 1][blocked_cells[i][1] - 1] = -1
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == -1:
					dp[i][j] = 0
				elif i == 0 and j == 0:
					dp[0][0] = 1
				else:
					if i > 0:
						dp[i][j] += dp[i - 1][j]
					if j > 0:
						dp[i][j] += dp[i][j - 1]
		return dp[m - 1][n - 1] % 1000000007


class Solution:

	def FindWays(self, n, m, blocked_cells):
		visit = [[0] * (m + 1) for _ in range(n + 1)]
		for i in blocked_cells:
			visit[i[0]][i[1]] = 1
		dp = {}

		def fun(visit, i, j):
			if i >= n + 1 or j >= m + 1:
				return 0
			if visit[i][j] == 1:
				return 0
			if i == n and j == m:
				return 1
			if (i, j) in dp:
				return dp[i, j]
			dp[i, j] = (fun(visit, i + 1, j) % 1000000007 + fun(visit, i, j + 1) % 1000000007) % 1000000007
			return dp[i, j]
		return fun(visit, 1, 1)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		if m == 0 or n == 0:
			return
		dp = [[0] * (m + 1) for _ in range(n + 1)]
		if [1, 1] not in blocked_cells:
			dp[0][1] = 1
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if [i, j] not in blocked_cells:
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[n][m] % 1000000007


class Solution:

	def FindWays(self, n, m, blocked_cells):
		if m == 0 or n == 0:
			return
		dp = [[0 for _ in range(m)] for _ in range(n)]
		for b in blocked_cells:
			dp[b[0] - 1][b[1] - 1] = -1
		if dp[0][0] == -1:
			return 0
		dp[0][0] = 1
		for i in range(1, n):
			if dp[i][0] == -1:
				break
			dp[i][0] = 1
		for j in range(1, m):
			if dp[0][j] == -1:
				break
			dp[0][j] = 1
		for i in range(1, n):
			for j in range(1, m):
				if dp[i][j] == -1:
					continue
				if dp[i - 1][j] != -1:
					dp[i][j] += dp[i - 1][j]
				if dp[i][j - 1] != -1:
					dp[i][j] += dp[i][j - 1]
		if dp[n - 1][m - 1] == -1:
			return 0
		return dp[n - 1][m - 1] % 1000000007


mod = 1000000007

class Solution:

	def FindWays(self, n, m, blocked_cells):
		grid = [[0 for j in range(m)] for i in range(n)]
		for (x, y) in blocked_cells:
			grid[x - 1][y - 1] = -1
		if grid[0][0] == -1:
			return 0
		for i in range(n):
			if grid[i][0] == 0:
				grid[i][0] = 1
			else:
				break
		for j in range(1, m):
			if grid[0][j] == 0:
				grid[0][j] = 1
			else:
				break
		for i in range(1, n):
			for j in range(1, m):
				if grid[i][j] != -1:
					if grid[i - 1][j] > 0:
						grid[i][j] += grid[i - 1][j]
					if grid[i][j - 1] > 0:
						grid[i][j] += grid[i][j - 1]
		return grid[n - 1][m - 1] % mod if grid[n - 1][m - 1] > 0 else 0


class Solution:

	def FindWays(self, n, m, blocked_cells):
		grid = [[0] * m for _ in range(n)]
		for (u, v) in blocked_cells:
			grid[u - 1][v - 1] = -1
		dp = [[-1] * m for _ in range(n)]
		mod = int(1000000000.0 + 7)
		for i in range(n):
			for j in range(m):
				if grid[i][j] == -1:
					dp[i][j] = 0
				elif i == 0 and j == 0:
					dp[i][j] = 1
				else:
					(up, left) = (0, 0)
					if i > 0:
						up = dp[i - 1][j]
					if j > 0:
						left = dp[i][j - 1]
					dp[i][j] = up + left
		return dp[n - 1][m - 1] % mod


class Solution:

	def FindWays(self, n, m, blocked_cells):
		isSourceRechable = self.isValid(blocked_cells, 0, 0, n, m)
		if isSourceRechable == False:
			return 0
		isDestinationRechable = self.isValid(blocked_cells, n - 1, m - 1, n, m)
		if isDestinationRechable == False:
			return 0
		else:
			dp = [0] * m
			dp[m - 1] = 1
			for i in range(m - 2, -1, -1):
				if self.isValid(blocked_cells, n - 1, i, n, m):
					dp[i] = dp[i + 1]
			for x in range(n - 2, -1, -1):
				temp = [0] * m
				for y in range(m - 1, -1, -1):
					right = down = 0
					if self.isValid(blocked_cells, x, y + 1, n, m):
						right = temp[y + 1]
					if self.isValid(blocked_cells, x + 1, y, n, m):
						down = dp[y]
					temp[y] = (right + down) % 1000000007
				dp = temp[:]
			return dp[0]

	def isValid(self, blocked, x, y, m, n):
		for each in blocked:
			if x == each[0] - 1 and y == each[1] - 1:
				return False
		if x >= 0 and x < m and (y >= 0) and (y < n):
			return True
		else:
			return False


class Solution:

	def FindWays(self, n, m, b):
		dp = [[-1] * (m + 1) for i in range(n + 1)]
		dp[1][1] = 1
		for x in b:
			dp[x[0]][x[1]] = 0
			if x[0] == n and x[1] == m:
				return 0

		def solve(i, j, dp):
			if i == 0 or j == 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			else:
				dp[i][j] = solve(i - 1, j, dp) + solve(i, j - 1, dp)
				return dp[i][j]
		solve(n, m, dp)
		return dp[n][m] % 1000000007


class Solution:

	def FindWays(self, n, m, blocked_cells):
		if not self.isValid(0, 0, n, m, blocked_cells):
			return 0
		if not self.isValid(n - 1, m - 1, n, m, blocked_cells):
			return 0
		dp = [-1] * m
		for row in range(n - 1, -1, -1):
			res = [-1] * m
			for col in range(m - 1, -1, -1):
				if row == n - 1 and col == m - 1:
					res[m - 1] = 1
					continue
				right = down = 0
				if self.isValid(row, col + 1, n, m, blocked_cells):
					right = res[col + 1]
				if self.isValid(row + 1, col, n, m, blocked_cells):
					down = dp[col]
				res[col] = (right + down) % 1000000007
			dp = res
		return dp[0]

	def process(self, row, col, n, m, blocked_cells, dp):
		if not self.isValid(row, col, n, m, blocked_cells):
			return 0
		if row == n - 1 and col == m - 1:
			return 1
		if dp[row][col] != -1:
			return dp[row][col]
		right = self.process(row, col + 1, n, m, blocked_cells, dp)
		down = self.process(row + 1, col, n, m, blocked_cells, dp)
		dp[row][col] = (right + down) % 1000000007
		return dp[row][col]

	def isValid(self, row, col, n, m, blocked_cells):
		for each in blocked_cells:
			if row == each[0] - 1 and col == each[1] - 1:
				return False
		if row >= 0 and row < n and (col >= 0) and (col < m):
			return True
		else:
			return False


class Solution:

	def FindWays(self, n, m, blocked_cells):
		self.dx = [0, 1]
		self.dy = [1, 0]
		self.dp = {}
		if [1, 1] in blocked_cells:
			return 0
		self.visited = [[False] * m for _ in range(n)]
		return int(self.solve(blocked_cells, n, m, 0, 0))

	def solve(self, blocked, n, m, x, y):
		if x == n - 1 and y == m - 1:
			return 1
		if (x, y) not in self.dp:
			count = 0
			self.visited[x][y] = True
			for i in range(2):
				x_new = x + self.dx[i]
				y_new = y + self.dy[i]
				if x_new < n and x_new >= 0 and (y_new < m) and (y_new >= 0) and ([x_new + 1, y_new + 1] not in blocked) and (self.visited[x_new][y_new] == False):
					count += self.solve(blocked, n, m, x_new, y_new)
			self.visited[x][y] = False
			self.dp[x, y] = count % (1000000000.0 + 7)
		return self.dp[x, y]


class Solution:

	def FindWays(self, n, m, blocked_cells):
		mod = 1000000000.0 + 7
		grid = [[0 for i in range(m)] for j in range(n)]
		for i in blocked_cells:
			x = i[0]
			y = i[1]
			grid[x - 1][y - 1] = -1
		for p in range(n):
			if grid[p][0] != -1:
				grid[p][0] = 1
			else:
				break
		for q in range(m):
			if grid[0][q] != -1:
				grid[0][q] = 1
			else:
				break
		for p in range(1, n, 1):
			for q in range(1, m, 1):
				if grid[p][q] == -1:
					continue
				if grid[p - 1][q] > 0:
					grid[p][q] += grid[p - 1][q]
				if grid[p][q - 1] > 0:
					grid[p][q] += grid[p][q - 1]
		if grid[n - 1][m - 1] == -1:
			return 0
		else:
			return int(grid[n - 1][m - 1] % mod)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		mod = 10 ** 9 + 7
		d = {}
		for (x, y) in blocked_cells:
			x -= 1
			y -= 1
			d[500 * x + y] = 1
		dp = [[1] * m for _ in range(n)]
		for i in range(n):
			for j in range(m):
				code = 500 * i + j
				if code in d:
					dp[i][j] = 0
				elif i > 0 and j > 0:
					dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
				elif i == 0:
					dp[i][j] = dp[i][j - 1]
				elif j == 0:
					dp[i][j] = dp[i - 1][j]
		return dp[-1][-1]


class Solution:

	def FindWays(self, n, m, blocked_cells):
		t = [[0 for i in range(m)] for i in range(n)]
		p = len(blocked_cells)
		for i in range(len(blocked_cells)):
			t[blocked_cells[i][0] - 1][blocked_cells[i][1] - 1] = -1
		if t[0][0] == -1:
			return 0
		for i in range(n):
			if t[i][0] == 0:
				t[i][0] = 1
			else:
				break
		for i in range(1, m, 1):
			if t[0][i] == 0:
				t[0][i] = 1
			else:
				break
		for i in range(1, n, 1):
			for j in range(1, m, 1):
				if t[i][j] == -1:
					continue
				if t[i - 1][j] > 0:
					t[i][j] = t[i][j] + t[i - 1][j]
				if t[i][j - 1] > 0:
					t[i][j] = t[i][j] + t[i][j - 1]
		if t[n - 1][m - 1] > 0:
			return t[n - 1][m - 1] % 1000000007
		else:
			return 0


class Solution:

	def FindWays(self, n, m, bcells):
		grid = [[1 for i in range(m)] for i in range(n)]
		for i in bcells:
			grid[i[0] - 1][i[1] - 1] = 0
		dp = {}

		def dfs(i, j):
			if i == n - 1 and j == m - 1 and (grid[i][j] == 1):
				return 1
			if i >= n or j >= m or grid[i][j] == 0:
				return 0
			if (i, j) in dp:
				return dp[i, j]
			dp[i, j] = (dfs(i + 1, j) + dfs(i, j + 1)) % 1000000007
			return dp[i, j]
		return dfs(0, 0)


MOD = int(1000000000.0 + 7)

def f(A, x, y, dp):
	N = len(A)
	M = len(A[0])
	if x < 0 or y < 0 or x >= N or (y >= M) or (A[x][y] == 1):
		return 0
	if x == N - 1 and y == M - 1:
		return 1
	if dp[x][y] != -1:
		return dp[x][y]
	ans = 0
	ans += f(A, x + 1, y, dp)
	ans += f(A, x, y + 1, dp)
	ans %= MOD
	dp[x][y] = ans
	return ans

class Solution:

	def FindWays(self, N, M, blocked_cells):
		dp = [[-1 for i in range(M)] for i in range(N)]
		A = [[0 for i in range(M)] for i in range(N)]
		for (x, y) in blocked_cells:
			x -= 1
			y -= 1
			if x == 0 and y == 0 or (x == N - 1 and y == M - 1):
				return 0
			A[x][y] = 1
		return f(A, 0, 0, dp)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		f = 10 ** 9 + 7
		dp = [[0 for i in range(m)] for j in range(n)]
		dp[0][0] = 1
		for s in blocked_cells:
			dp[s[0] - 1][s[1] - 1] = -1
		if dp[0][0] == -1 or dp[n - 1][m - 1] == -1:
			return 0
		for i in range(n):
			for j in range(m):
				p = 0
				q = 0
				if i >= 0 and dp[i - 1][j] != -1:
					p = dp[i - 1][j]
				if j - 1 >= 0 and dp[i][j - 1] != -1:
					q = dp[i][j - 1]
				if dp[i][j] != -1:
					dp[i][j] = (p % f + q % f) % f
				if i == 0 and j == 0:
					dp[i][j] = 1
		return dp[n - 1][m - 1]

		def recurs(blocks, n, m):
			if n == 0 and m == 0:
				if [n + 1, m + 1] not in blocks:
					return 1
				else:
					return 0
			else:
				p = 0
				q = 0
				if n - 1 >= 0 and [n + 1, m + 1] not in blocks:
					p = recurs(blocks, n - 1, m)
				if m - 1 >= 0 and [n + 1, m + 1] not in blocks:
					q = recurs(blocks, n, m - 1)
				return p + q
		return recurs(blocked_cells, n - 1, m - 1)


class Solution:

	def FindWays(self, n, m, b):
		d = {}
		for i in b:
			k = str(i[0]) + ',' + str(i[1])
			d[k] = 0
		if str(n) + ',' + str(m) in d or str(1) + ',' + str(1) in d:
			return 0

		def r(n, m, mo={}):
			k = str(n) + ',' + str(m)
			if m == 1 and n == 1:
				return 1
			if m == 0 or n == 0:
				return 0
			if k in d:
				return 0
			if k in mo:
				return mo[k]
			mo[k] = (r(n - 1, m, mo) + r(n, m - 1, mo)) % (10 ** 9 + 7)
			return mo[k]
		return r(n, m, {})


class Solution:

	def FindWays(self, n, m, blocked_cells):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		dp[1][1] = 1
		for i in blocked_cells:
			dp[i[0]][i[1]] = -1
		if dp[n][m] == -1:
			return 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if dp[i][j] == -1:
					continue
				if dp[i - 1][j] != -1:
					dp[i][j] += dp[i - 1][j]
				if dp[i][j - 1] != -1:
					dp[i][j] += dp[i][j - 1]
		return dp[n][m] % 1000000007


class Solution:

	def FindWays(self, n, m, blocked_cells):
		dp = [[0] * m for i in range(n)]
		if [1, 1] not in blocked_cells:
			dp[0][0] = 1
		for i in range(1, n):
			if [i + 1, 1] in blocked_cells:
				continue
			dp[i][0] = dp[i - 1][0]
		for i in range(1, m):
			if [1, i + 1] in blocked_cells:
				continue
			dp[0][i] = dp[0][i - 1]
		for i in range(1, n):
			for j in range(1, m):
				if [i + 1, j + 1] in blocked_cells:
					continue
				else:
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for cell in blocked_cells:
			r = cell[0]
			c = cell[1]
			dp[r][c] = -1
		if dp[1][1] == -1 or dp[n][m] == -1:
			return 0
		else:
			dp[n][m] = 1
		for r in range(n, 0, -1):
			for c in range(m, 0, -1):
				if dp[r][c] != -1:
					right = 0
					down = 0
					if c + 1 <= m and dp[r][c + 1] != -1:
						right = dp[r][c + 1]
					if r + 1 <= n and dp[r + 1][c] != -1:
						down = dp[r + 1][c]
					dp[r][c] += (right % 1000000007 + down % 1000000007) % 1000000007
		return dp[1][1]


class Solution:

	def FindWays(self, n, m, blocked_cells):
		MOD = 10 ** 9 + 7
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		dp[1][1] = 1
		for x in blocked_cells:
			dp[x[0]][x[1]] = -1
		if dp[n][m] == -1:
			return 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if dp[i][j] == -1:
					continue
				if dp[i - 1][j] != -1:
					dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD
				if dp[i][j - 1] != -1:
					dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD
		return dp[n][m]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m, k) = input().split()
		n = int(n)
		m = int(m)
		k = int(k)
		blocked_cells = []
		for i in range(k):
			a = list(map(int, input().split()))
			blocked_cells.append(a)
		obj = Solution()
		ans = obj.FindWays(n, m, blocked_cells)
		print(ans)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		isSourceRechable = self.isValid(blocked_cells, 0, 0, n, m)
		if isSourceRechable == False:
			return 0
		isDestinationRechable = self.isValid(blocked_cells, n - 1, m - 1, n, m)
		if isDestinationRechable == False:
			return 0
		else:
			dp = [0] * m
			dp[m - 1] = 1
			for i in range(m - 2, -1, -1):
				if self.isValid(blocked_cells, n - 1, i, n, m):
					dp[i] = dp[i + 1]
			for x in range(n - 2, -1, -1):
				temp = [0] * m
				for y in range(m - 1, -1, -1):
					right = down = 0
					if self.isValid(blocked_cells, x, y + 1, n, m):
						right = temp[y + 1]
					if self.isValid(blocked_cells, x + 1, y, n, m):
						down = dp[y]
					temp[y] = (right + down) % 1000000007
				dp = temp[:]
			return dp[0]

	def isValid(self, blocked, x, y, m, n):
		for each in blocked:
			if x == each[0] - 1 and y == each[1] - 1:
				return False
		if x >= 0 and x < m and (y >= 0) and (y < n):
			return True
		else:
			return False
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m, k) = input().split()
		n = int(n)
		m = int(m)
		k = int(k)
		blocked_cells = []
		for i in range(k):
			a = list(map(int, input().split()))
			blocked_cells.append(a)
		obj = Solution()
		ans = obj.FindWays(n, m, blocked_cells)
		print(ans)


def solve(board, n, m):
	if board[0][0] == -1 or board[n - 1][m - 1] == -1:
		return 0
	for i in range(m):
		if board[0][i] == 0:
			board[0][i] = 1
		else:
			break
	for i in range(1, n):
		if board[i][0] == 0:
			board[i][0] = 1
		else:
			break
	for i in range(1, n):
		for j in range(1, m):
			if board[i][j] == -1:
				continue
			if board[i - 1][j] > 0:
				board[i][j] = board[i - 1][j] + board[i][j]
			if board[i][j - 1] > 0:
				board[i][j] = board[i][j - 1] + board[i][j]
	return board[n - 1][m - 1] % (10 ** 9 + 7)

class Solution:

	def FindWays(self, n, m, blocked_cells):
		board = [[0 for i in range(m)] for i in range(n)]
		for (i, j) in blocked_cells:
			board[i - 1][j - 1] = -1
		ret = solve(board, n, m)
		return ret
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m, k) = input().split()
		n = int(n)
		m = int(m)
		k = int(k)
		blocked_cells = []
		for i in range(k):
			a = list(map(int, input().split()))
			blocked_cells.append(a)
		obj = Solution()
		ans = obj.FindWays(n, m, blocked_cells)
		print(ans)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		grid = [[0 for _ in range(m)] for _ in range(n)]
		for i in blocked_cells:
			grid[i[0] - 1][i[1] - 1] = -1
		if grid[0][0] == -1 or grid[n - 1][m - 1] == -1:
			return 0
		for i in range(n):
			if grid[i][0] == 0:
				grid[i][0] = 1
			else:
				break
		for i in range(1, m):
			if grid[0][i] == 0:
				grid[0][i] = 1
			else:
				break
		for i in range(1, n):
			for j in range(1, m):
				if grid[i][j] == -1:
					continue
				if grid[i - 1][j] > 0:
					grid[i][j] = grid[i][j] + grid[i - 1][j]
				if grid[i][j - 1] > 0:
					grid[i][j] = grid[i][j] + grid[i][j - 1]
		if grid[n - 1][m - 1] > 0:
			return grid[n - 1][m - 1] % 1000000007
		else:
			return 0


class Solution:

	def FindWays(self, n, m, blocked_cells):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		mat = [[1 for i in range(m + 1)] for j in range(n + 1)]
		dp[1][1] = 1
		for i in blocked_cells:
			dp[i[0]][i[1]] = -1
		if dp[n][m] == -1:
			return 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if dp[i][j] == -1:
					continue
				if dp[i - 1][j] != -1:
					dp[i][j] += dp[i - 1][j]
				if dp[i][j - 1] != -1:
					dp[i][j] += dp[i][j - 1]
		return dp[n][m] % 1000000007
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, m, k) = input().split()
		n = int(n)
		m = int(m)
		k = int(k)
		blocked_cells = []
		for i in range(k):
			a = list(map(int, input().split()))
			blocked_cells.append(a)
		obj = Solution()
		ans = obj.FindWays(n, m, blocked_cells)
		print(ans)


class Solution:

	@staticmethod
	def findWays(rows, cols, x_index, y_index, blockedCellHash, findWayHash):
		if x_index > rows or y_index > cols:
			return 0
		if x_index == rows and y_index == cols:
			return 1
		key = (x_index, y_index)
		if key in findWayHash:
			return findWayHash[key]
		(downWays, rightWays) = (0, 0)
		if (x_index + 1, y_index) not in blockedCellHash:
			downWays = Solution.findWays(rows, cols, x_index + 1, y_index, blockedCellHash, findWayHash)
		if (x_index, y_index + 1) not in blockedCellHash:
			rightWays = Solution.findWays(rows, cols, x_index, y_index + 1, blockedCellHash, findWayHash)
		totalWays = downWays + rightWays
		findWayHash[key] = totalWays
		return findWayHash[key]

	def FindWays(self, n, m, blocked_cells):
		rows = n - 1
		cols = m - 1
		blockedCellHash = dict()
		for cell in blocked_cells:
			(x_index, y_index) = cell
			new_x_index = x_index - 1
			new_y_index = y_index - 1
			blockedCellHash[new_x_index, new_y_index] = 0
		if (0, 0) in blockedCellHash or (rows, cols) in blockedCellHash:
			return 0
		findWayHash = dict()
		op = Solution.findWays(rows, cols, 0, 0, blockedCellHash, findWayHash)
		return op % (10 ** 9 + 7)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		grid = [[0 for i in range(m)] for i in range(n)]
		for (i, j) in blocked_cells:
			grid[i - 1][j - 1] = 1
		dp = [[0 for i in range(m)] for i in range(n)]
		for col in range(m):
			if grid[0][col] == 1:
				break
			dp[0][col] = 1
		for row in range(n):
			if grid[row][0] == 1:
				break
			dp[row][0] = 1
		for row in range(1, n):
			for col in range(1, m):
				if grid[row][col] == 1:
					dp[row][col] = 0
				else:
					dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def FindWays(self, m, n, blocked_cells):
		dp = [[0 for i in range(n)] for j in range(m)]
		p = 0
		q = 0
		for i in range(n):
			if [1, i + 1] in blocked_cells:
				p = 1
			if p == 0 and i != 0:
				dp[0][i] = 1
		for i in range(m):
			if [i + 1, 1] in blocked_cells:
				q = 1
			if q == 0 and i != 0:
				dp[i][0] = 1
		for i in range(1, m):
			for j in range(1, n):
				if [i + 1, j + 1] not in blocked_cells:
					dp[i][j] += dp[i - 1][j] + dp[i][j - 1]
				else:
					dp[i][j] = 0
		return dp[m - 1][n - 1] % 1000000007


class Solution:

	def FindWays(self, n, m, blocked_cells):
		mod = 10 ** 9 + 7
		blocked = set([tuple(x) for x in blocked_cells])
		if (n, m) in blocked:
			return 0
		dp = [0] * (m + 1)
		temp = [0] * (m + 1)
		for i in range(1, n + 1):
			temp = [0] * (m + 1)
			for j in range(1, m + 1):
				if (i, j) in blocked:
					temp[j] = 0
				elif i == 1 and j == 1:
					temp[j] = 1
				else:
					up = 0
					left = 0
					if i > 1:
						up = dp[j]
					if j > 1:
						left = temp[j - 1]
					temp[j] = (up + left) % mod
			dp = temp
		return dp[m]


from functools import lru_cache
mod = 10 ** 9 + 7

class Solution:

	def FindWays(self, n, m, blocked_cells):
		blocked = {tuple(b): True for b in blocked_cells}

		@lru_cache(None)
		def dfs(x, y):
			if x < 1 or y < 1 or x > n or (y > m) or ((x, y) in blocked):
				return 0
			if x == n and y == m:
				return 1
			return dfs(x + 1, y) + dfs(x, y + 1)
		return dfs(1, 1) % mod


class Solution:

	def FindWays(self, n, m, blocked_cells):
		dp = [[1 for i in range(m)] for j in range(n)]
		for (x, y) in blocked_cells:
			dp[x - 1][y - 1] = 0
		row_value = 1
		for i in range(n):
			if dp[i][0] == 0:
				row_value = 0
			dp[i][0] = row_value
		col_value = 1
		for i in range(m):
			if dp[0][i] == 0:
				col_value = 0
			dp[0][i] = col_value
		mod = 10 ** 9 + 7
		for i in range(1, n):
			for j in range(1, m):
				if dp[i][j] != 0:
					dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
		return dp[-1][-1]


class Solution:

	def FindWays(self, n, m, blocked_cells):
		d = {}
		for i in blocked_cells:
			val = str(i[0]) + ',' + str(i[1])
			d[val] = 0
		if str(n) + ',' + str(m) in d or str(1) + ',' + str(1) in d:
			return 0

		def helper(n, m, res={}):
			val = str(n) + ',' + str(m)
			if m == 1 and n == 1:
				return 1
			if m == 0 or n == 0:
				return 0
			if val in d:
				return 0
			if val in res:
				return res[val]
			res[val] = (helper(n - 1, m, res) + helper(n, m - 1, res)) % (10 ** 9 + 7)
			return res[val]
		return helper(n, m, {})


class Solution:

	def FindWays(self, n, m, blocked_cells):
		blo = set()
		mod = pow(10, 9) + 7
		for (i, j) in blocked_cells:
			blo.add((i, j))
		dp = [[0 for i in range(m)] for j in range(n)]
		if (1, 1) not in blo:
			dp[0][0] = 1
		for i in range(n):
			for j in range(m):
				if i == 0 and j == 0:
					continue
				if (i + 1, j + 1) in blo:
					continue
				if i == 0:
					dp[i][j] = dp[i][j - 1]
					continue
				if j == 0:
					dp[i][j] = dp[i - 1][j]
					continue
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[-1][-1] % mod


class Solution:

	def FindWays(self, n, m, blocked_cells):
		dp = {}
		dp[1, 1] = 1
		for (a, b) in blocked_cells:
			dp[a, b] = 0

		def dfs(n, m):
			if (n, m) in dp:
				return dp[n, m]
			if n < 1 or m < 1:
				dp[n, m] = 0
				return 0
			dp[n, m] = dfs(n - 1, m) + dfs(n, m - 1)
			return dp[n, m]
		return dfs(n, m) % (10 ** 9 + 7)


class Solution:

	def f(self, cr, cc, n, m, d, dp):
		if cr == n and cc == m:
			return 1
		if cr > n or cc > m:
			return 0
		a1 = a2 = 0
		state = (cr, cc)
		if state in dp:
			return dp[state]
		if (cr + 1, cc) not in d:
			a1 = self.f(cr + 1, cc, n, m, d, dp)
		if (cr, cc + 1) not in d:
			a2 = self.f(cr, cc + 1, n, m, d, dp)
		ans = a1 + a2
		dp[state] = ans % (10 ** 9 + 7)
		return dp[state]

	def FindWays(self, n, m, blocked_cells):
		d = {}
		cr = cc = 1
		for i in blocked_cells:
			d[tuple(i)] = 1
		if (cr, cc) in d:
			return 0
		dp = {}
		return self.f(cr, cc, n, m, d, dp)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		M = [[0 for j in range(m)] for i in range(n)]
		for (i, j) in blocked_cells:
			M[i - 1][j - 1] = 1
		for i in range(n):
			for j in range(m):
				if M[i][j] == 0:
					M[i][j] = 1
				else:
					M[i][j] = 0
		for j in range(1, m):
			if M[0][j - 1] == 0 or M[0][j] == 0:
				M[0][j] = 0
			else:
				M[0][j] = 1
		for i in range(1, n):
			if M[i - 1][0] == 0 or M[i][0] == 0:
				M[i][0] = 0
			else:
				M[i][0] = 1
		for i in range(1, n):
			for j in range(1, m):
				if M[i][j] != 0:
					M[i][j] = M[i - 1][j] + M[i][j - 1]
		return M[-1][-1] % (10 ** 9 + 7)


M = 10 ** 9 + 7

class Solution:

	def FindWays(self, n, m, blocked_cells):
		dp = [[0] * m for _ in range(n)]
		for (i, j) in blocked_cells:
			dp[i - 1][j - 1] = -1
		if dp[0][0] == -1 or dp[n - 1][m - 1] == -1:
			return 0
		dp[0][0] = 1
		for j in range(1, m):
			if dp[0][j - 1] != -1 and dp[0][j] != -1:
				dp[0][j] = 1
			else:
				dp[0][j] = -1
		for i in range(1, n):
			if dp[i - 1][0] != -1 and dp[i][0] != -1:
				dp[i][0] = 1
			else:
				dp[i][0] = -1
		for i in range(1, n):
			for j in range(1, m):
				if dp[i][j] != -1:
					if dp[i - 1][j] == -1 and dp[i][j - 1] == -1:
						dp[i][j] = -1
					elif dp[i - 1][j] == -1 or dp[i][j - 1] == -1:
						dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
					else:
						dp[i][j] = (dp[i - 1][j] % M + dp[i][j - 1] % M) % M
		if dp[n - 1][m - 1] > 0:
			return dp[n - 1][m - 1]
		else:
			return 0


class Solution:

	def FindWays(self, n, m, blocked_cells):
		matrix = [[0 for j in range(m)] for i in range(n)]
		for i in blocked_cells:
			matrix[i[0] - 1][i[1] - 1] = -1
		if matrix[0][0] == -1:
			return 0
		for i in range(n):
			if matrix[i][0] == 0:
				matrix[i][0] = 1
			else:
				break
		for j in range(1, m):
			if matrix[0][j] == 0:
				matrix[0][j] = 1
			else:
				break
		for i in range(1, n):
			for j in range(1, m):
				if matrix[i][j] == -1:
					continue
				if matrix[i - 1][j] > 0:
					matrix[i][j] += matrix[i - 1][j]
				if matrix[i][j - 1] > 0:
					matrix[i][j] += matrix[i][j - 1]
		if matrix[n - 1][m - 1] > 0:
			return matrix[n - 1][m - 1] % 1000000007
		return 0


class Solution:

	def FindWays(self, n, m, blocked_cells):
		MOD = 10 ** 9 + 7
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		dp[1][1] = 1
		for x in blocked_cells:
			dp[x[0]][x[1]] = -1
		if dp[n][m] == -1:
			return 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if dp[i][j] == -1:
					continue
				if dp[i - 1][j] != -1:
					dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD
				if dp[i][j - 1] != -1:
					dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD
		return dp[n][m]


class Solution:

	def FindWays(self, n, m, blocked_cells):
		dp = [[0 for i in range(m)] for i in range(n)]
		for i in blocked_cells:
			dp[i[0] - 1][i[1] - 1] = -1
		if dp[0][0] == -1 or dp[n - 1][m - 1] == -1:
			return 0
		dp[n - 1][m - 1] = 1
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				if i == n - 1 and j == m - 1:
					dp[i][j] = 1
				elif dp[i][j] != -1:
					if i == n - 1:
						dp[i][j] = dp[i][j + 1]
					elif j == m - 1:
						dp[i][j] = dp[i + 1][j]
					elif dp[i + 1][j] + dp[i][j + 1] == -2:
						dp[i][j] = -1
					elif dp[i + 1][j] == -1:
						dp[i][j] = dp[i][j + 1]
					elif dp[i][j + 1] == -1:
						dp[i][j] = dp[i + 1][j]
					else:
						dp[i][j] = dp[i + 1][j] + dp[i][j + 1]
		if dp[0][0] == -1:
			return 0
		else:
			return dp[0][0] % 1000000007


class Solution:

	def is_valid(self, i, j, n, m):
		if i < 0 or j < 0 or i >= n or (j >= m):
			return False
		return True

	def recurse(self, mat, i, j, n, m, blocked_cells_set):
		if not self.is_valid(i, j, n, m):
			return 0
		if i == n - 1 and j == m - 1:
			return 1
		if mat[i][j] != -1:
			return mat[i][j]
		mat[i][j] = self.recurse(mat, i + 1, j, n, m, blocked_cells_set) + self.recurse(mat, i, j + 1, n, m, blocked_cells_set)
		return mat[i][j]

	def FindWays(self, n, m, blocked_cells):
		mat = []
		for i in range(n):
			mat.append([-1] * m)
		for val in blocked_cells:
			mat[val[0] - 1][val[1] - 1] = 0
		if mat[n - 1][m - 1] == 0:
			return 0
		return self.recurse(mat, 0, 0, n, m, blocked_cells) % (10 ** 9 + 7)


MOD = 1000000007

class Solution:

	def FindWays(self, n, m, bc):
		memo = [[0 for _ in range(m)] for _ in range(n)]
		memo[0][0] = 0 if [1, 1] in bc else 1
		for i in range(n):
			for j in range(m):
				if i + 1 < n and (not [i + 1 + 1, j + 1] in bc):
					memo[i + 1][j] += memo[i][j]
					memo[i + 1][j] %= MOD
				if j + 1 < m and (not [i + 1, j + 1 + 1] in bc):
					memo[i][j + 1] += memo[i][j]
					memo[i][j + 1] %= MOD
		return memo[-1][-1]


class Solution:

	def FindWays(self, n, m, b):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(len(b)):
			dp[b[i][0]][b[i][1]] = -1
		dp[0][1] = 1
		mod = 10 ** 9 + 7
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if dp[i][j] == -1:
					dp[i][j] = 0
				else:
					dp[i][j] = (dp[i - 1][j] % mod + dp[i][j - 1] % mod) % mod
		return dp[n][m] % mod


class Solution:

	def FindWays(self, n, m, bc):
		arr = [[0] * (m + 1) for i in range(n + 1)]
		for (r, c) in bc:
			arr[r][c] = -1
		if arr[1][1] == -1 or arr[n][m] == -1:
			return 0
		arr[1][1] = 1
		a = 10 ** 9 + 7
		for i in range(2, n + 1):
			if arr[i][1] == -1:
				break
			arr[i][1] = 1
		for j in range(2, m + 1):
			if arr[1][j] == -1:
				break
			arr[1][j] = 1
		for i in range(2, n + 1):
			for j in range(2, m + 1):
				if arr[i][j] != -1:
					r = arr[i][j - 1] if arr[i][j - 1] != -1 else 0
					d = arr[i - 1][j] if arr[i - 1][j] != -1 else 0
					arr[i][j] = (r + d) % a
		return arr[n][m]


class Solution:

	def FindWays(self, n, m, blocked_cells):
		s = set()
		for k in blocked_cells:
			s.add(tuple(k))
		dp = [[-1] * m for i in range(n)]

		def recur(i, j):
			if i > n or j > m or (i, j) in s:
				return 0
			if i == n and j == m:
				return 1
			if dp[i - 1][j - 1] != -1:
				return dp[i - 1][j - 1]
			else:
				ways = recur(i + 1, j) + recur(i, j + 1)
				dp[i - 1][j - 1] = ways
				return ways
		return recur(1, 1) % (10 ** 9 + 7)


class Solution:

	def FindWays(self, R, C, blocked):
		maze = [[0 for j in range(C)] for i in range(R)]
		for b in blocked:
			maze[b[0] - 1][b[1] - 1] = -1
		if maze[0][0] == -1 or maze[R - 1][C - 1] == -1:
			return 0
		for i in range(R):
			if maze[i][0] == 0:
				maze[i][0] = 1
			else:
				break
		for i in range(1, C, 1):
			if maze[0][i] == 0:
				maze[0][i] = 1
			else:
				break
		for i in range(1, R, 1):
			for j in range(1, C, 1):
				if maze[i][j] == -1:
					continue
				if maze[i - 1][j] > 0:
					maze[i][j] = maze[i][j] + maze[i - 1][j]
				if maze[i][j - 1] > 0:
					maze[i][j] = maze[i][j] + maze[i][j - 1]
		return maze[R - 1][C - 1] % (10 ** 9 + 7)


class Solution:

	def FindWays(self, m, n, blocked_cells):
		obstacleGrid = [[0] * n for _ in range(m)]
		for (i, j) in blocked_cells:
			obstacleGrid[i - 1][j - 1] = 1
		dp = [[0] * n for _ in range(m)]
		for i in range(m):
			if obstacleGrid[i][0] == 1:
				break
			else:
				dp[i][0] = 1
		for i in range(n):
			if obstacleGrid[0][i] == 1:
				break
			else:
				dp[0][i] = 1
		for i in range(1, m):
			for j in range(1, n):
				if obstacleGrid[i][j] == 1:
					dp[i][j] = 0
				else:
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[-1][-1] % 1000000007


class Solution:

	def FindWays(self, n, m, bld):
		d = dict()
		for i in bld:
			d[tuple(i)] = 1
		if d.get((n, m), 0) == 1 or d.get((1, 1), 0) == 1:
			return 0
		dp = [[0 for i in range(m)] for j in range(n)]
		dp[0][0] = 1
		z = 1
		for i in range(1, m):
			if d.get((1, i + 1), 0) == 1:
				z = 0
			dp[0][i] = z
		z = 1
		for i in range(1, n):
			if d.get((i + 1, 1), 0) == 1:
				z = 0
			dp[i][0] = z
		mod = 1000000007
		for i in range(1, n):
			for j in range(1, m):
				if d.get((i + 1, j + 1), 0) == 1:
					dp[i][j] = 0
				elif dp[i - 1][j] != 0 and dp[i][j - 1] != 0:
					dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) % mod
		return dp[n - 1][m - 1]


class Solution:

	def FindWays(self, n, m, bloc):
		dp = [[0] * (m + 1) for i in range(n + 1)]
		ss = set()
		for i in bloc:
			ss.add(tuple(i))
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if i == 1 and j == 1:
					dp[i][j] = 1
					continue
				if (i, j - 1) not in ss:
					dp[i][j] += dp[i][j - 1]
				if (i - 1, j) not in ss:
					dp[i][j] += dp[i - 1][j]
		if (n, m) in ss:
			return 0
		return dp[n][m] % (10 ** 9 + 7)


class Solution:

	def FindWays(self, n, m, blocked):
		self.ans = 0
		self.dp = [[-1 for _ in range(m)] for _ in range(n)]
		self.arr = [[1 for _ in range(m)] for _ in range(n)]
		for i in range(len(blocked)):
			self.arr[blocked[i][0] - 1][blocked[i][1] - 1] = 0

		def dfs(x, y, n, m):
			if self.dp[x][y] != -1:
				return self.dp[x][y]
			if x == n - 1 and y == m - 1 and self.arr[x][y]:
				self.dp[x][y] = 1
				return self.dp[x][y]
			total = 0
			if x < n - 1 and y <= m - 1 and self.arr[x + 1][y]:
				total += dfs(x + 1, y, n, m)
			if x <= n - 1 and y < m - 1 and self.arr[x][y + 1]:
				total += dfs(x, y + 1, n, m)
			self.dp[x][y] = total
			return self.dp[x][y]
		if self.arr[0][0] == 0:
			return 0
		dfs(0, 0, n, m)
		return self.dp[0][0] % (10 ** 9 + 7)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		l = [[0] * m for i in range(n)]
		k = 0
		d = 0
		for i in range(len(blocked_cells)):
			k = blocked_cells[i][0] - 1
			d = blocked_cells[i][1] - 1
			l[k][d] = -1
		for i in range(n):
			if l[i][0] == -1:
				break
			else:
				l[i][0] = 1
		for i in range(m):
			if l[0][i] == -1:
				break
			else:
				l[0][i] = 1
		for i in range(1, n):
			for j in range(1, m):
				if l[i][j] == -1:
					continue
				if l[i][j - 1] != -1:
					l[i][j] += l[i][j - 1]
				if l[i - 1][j] != -1:
					l[i][j] += l[i - 1][j]
		if l[n - 1][m - 1] == -1:
			return 0
		else:
			return l[n - 1][m - 1] % 1000000007


class Solution:

	def FindWays(self, R, C, blocked_cells):
		mat = [[0 for _ in range(C + 1)] for _ in range(R + 1)]
		for (x, y) in blocked_cells:
			mat[x][y] = -1
		mod = 10 ** 9 + 7
		mat[0][1] = 1
		for row in range(1, R + 1):
			for col in range(1, C + 1):
				if mat[row][col] == -1:
					mat[row][col] = 0
				else:
					mat[row][col] = (mat[row - 1][col] % mod + mat[row][col - 1] % mod) % mod
		return mat[R][C]


class Solution:

	def FindWays(self, n, m, blocked_cells):
		l = [[0] * m for i in range(n)]
		for i in blocked_cells:
			x = i[0] - 1
			y = i[1] - 1
			l[x][y] = 1
		if l[0][0] == 1:
			return 0
		else:
			l[0][0] = 1
			for i in range(1, n):
				l[i][0] = int(l[i][0] == 0 and l[i - 1][0] == 1)
			for i in range(1, m):
				l[0][i] = int(l[0][i] == 0 and l[0][i - 1] == 1)
			for i in range(1, n):
				for j in range(1, m):
					if l[i][j] == 0:
						l[i][j] = l[i - 1][j] + l[i][j - 1]
					else:
						l[i][j] = 0
			return l[-1][-1] % (10 ** 9 + 7)


class Solution:

	def FindWays(self, n, m, bc):
		arr = [[1 for _ in range(m)] for i in range(n)]
		MOD = 10 ** 9 + 7
		for i in range(m):
			if [1, i + 1] in bc:
				arr[0][i] = 0
			else:
				arr[0][i] = arr[0][i - 1]
		for i in range(n):
			if [i + 1, 1] in bc:
				arr[i][0] = 0
			else:
				arr[i][0] = arr[i - 1][0]
		for i in range(1, n):
			for j in range(1, m):
				if [i + 1, j + 1] not in bc:
					arr[i][j] = arr[i - 1][j] + arr[i][j - 1]
				else:
					arr[i][j] = 0
		return arr[n - 1][m - 1] % MOD


class Solution:

	def FindWays(self, n, m, blocked_cells):
		mat = [[0 for j in range(m)] for i in range(n)]
		for (x, y) in blocked_cells:
			mat[x - 1][y - 1] = -1
		blocked_cells = mat
		for i in range(n):
			for j in range(m):
				if blocked_cells[i][j] == -1:
					continue
				if i == 0 and j == 0:
					blocked_cells[i][j] = 1
					continue
				if i == 0:
					blocked_cells[i][j] = blocked_cells[i][j - 1]
					continue
				if j == 0:
					blocked_cells[i][j] = blocked_cells[i - 1][j]
					continue
				if blocked_cells[i][j - 1] > 0:
					blocked_cells[i][j] = blocked_cells[i][j] + blocked_cells[i][j - 1]
				if blocked_cells[i - 1][j] > 0:
					blocked_cells[i][j] = blocked_cells[i][j] + blocked_cells[i - 1][j]
		return (0 if blocked_cells[n - 1][m - 1] == -1 else blocked_cells[n - 1][m - 1]) % 1000000007


class Solution:

	def FindWays(self, n, m, blocked_cells):
		maze = [[0 for j in range(m)] for i in range(n)]
		for b in blocked_cells:
			maze[b[0] - 1][b[1] - 1] = -1
		if maze[0][0] == -1 or maze[n - 1][m - 1] == -1:
			return 0
		for i in range(n):
			if maze[i][0] == 0:
				maze[i][0] = 1
			else:
				break
		for i in range(1, m, 1):
			if maze[0][i] == 0:
				maze[0][i] = 1
			else:
				break
		for i in range(1, n):
			for j in range(1, m):
				if maze[i][j] == -1:
					continue
				if maze[i - 1][j] > 0:
					maze[i][j] = maze[i][j] + maze[i - 1][j]
				if maze[i][j - 1] > 0:
					maze[i][j] = maze[i][j] + maze[i][j - 1]
		return maze[n - 1][m - 1] % (10 ** 9 + 7)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		mod = 1000000007
		count = 0
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for cell in blocked_cells:
			dp[cell[0]][cell[1]] = -1
		if dp[1][1] == -1:
			return 0
		for i in range(1, n + 1):
			if dp[i][1] == -1:
				break
			dp[i][1] = 1
		for j in range(1, m + 1):
			if dp[1][j] == -1:
				break
			dp[1][j] = 1
		for i in range(2, n + 1):
			for j in range(2, m + 1):
				if dp[i][j] == -1:
					dp[i][j] = 0
					continue
				if dp[i - 1][j] > 0:
					dp[i][j] += dp[i - 1][j] % mod
				if dp[i][j - 1] > 0:
					dp[i][j] += dp[i][j - 1] % mod
		if dp[n][m] > 0:
			return dp[n][m] % mod
		else:
			return 0


class Solution:

	def FindWays(self, n, m, blocked_cells):
		mod = 1000000007
		if [n, m] in blocked_cells:
			return 0
		max_row_cross = -1
		for cell in blocked_cells:
			if cell[0] == n:
				max_row_cross = max(max_row_cross, cell[1] - 1)
		max_col_cross = -1
		for cell in blocked_cells:
			if cell[1] == m:
				max_col_cross = max(max_col_cross, cell[0] - 1)
		dp = [[0] * m for _ in range(n)]
		for cell in blocked_cells:
			dp[cell[0] - 1][cell[1] - 1] = -1
		for i in range(m):
			if i > max_row_cross:
				dp[n - 1][i] = 1
			else:
				dp[n - 1][i] = 0
		for j in range(n):
			if j > max_col_cross:
				dp[j][m - 1] = 1
			else:
				dp[j][m - 1] = 0
		for i in range(n - 2, -1, -1):
			for j in range(m - 2, -1, -1):
				if dp[i][j] != -1:
					dp[i][j] = dp[i + 1][j] + dp[i][j + 1]
				else:
					dp[i][j] = 0
		return dp[0][0] % mod


class Solution:

	def solve(self, n, m, b, t):
		if t[n][m] != -1:
			return t[n][m]
		if (n, m) in b:
			return 0
		elif n == 1 and m == 1:
			return 1
		elif n == 1:
			return self.solve(n, m - 1, b, t)
		elif m == 1:
			return self.solve(n - 1, m, b, t)
		t[n][m] = self.solve(n, m - 1, b, t) + self.solve(n - 1, m, b, t)
		return t[n][m]

	def FindWays(self, n, m, b):
		k = 1000000007
		t = [[-1] * (m + 1) for _ in range(n + 1)]
		s = set((tuple(i) for i in b))
		ans = self.solve(n, m, s, t)
		return ans % k


class Solution:

	def FindWays(self, n, m, blocked_cells):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		for i in range(len(blocked_cells)):
			dp[blocked_cells[i][0]][blocked_cells[i][1]] = -1
		if dp[1][1] == -1:
			return 0
		dp[1][1] = 1
		for i in range(2, m + 1):
			if dp[1][i] != -1 and dp[1][i - 1] != -1:
				dp[1][i] = dp[1][i - 1] + dp[0][i]
		for j in range(2, n + 1):
			if dp[j][1] != -1 and dp[j - 1][1] != -1:
				dp[j][1] = dp[j - 1][1] + dp[j][0]
		for i in range(2, n + 1):
			for j in range(2, m + 1):
				if dp[i][j - 1] != -1 and dp[i - 1][j] != -1 and (dp[i][j] != -1):
					dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
				elif dp[i][j - 1] != -1 and dp[i - 1][j] == -1 and (dp[i][j] != -1):
					dp[i][j] = dp[i][j - 1]
				elif dp[i][j - 1] == -1 and dp[i - 1][j] != -1 and (dp[i][j] != -1):
					dp[i][j] = dp[i - 1][j]
		if dp[n][m] == -1:
			return 0
		return dp[n][m] % (10 ** 9 + 7)


class Solution:

	def FindWays(self, n, m, blocked_cells):
		dic = {}
		for i in blocked_cells:
			dic[tuple([i[0] - 1, i[1] - 1])] = 1
		dp = [[-1 for i in range(0, m)] for j in range(0, n)]
		for j in range(0, m):
			if (0, j) in dic.keys() or (j - 1 >= 0 and dp[0][j - 1] == 0):
				dp[0][j] = 0
			else:
				dp[0][j] = 1
		for i in range(0, n):
			if (i, 0) in dic.keys() or (i - 1 >= 0 and dp[i - 1][0] == 0):
				dp[i][0] = 0
			else:
				dp[i][0] = 1
		for i in range(1, n):
			for j in range(1, m):
				if (i, j) in dic.keys():
					dp[i][j] = 0
				else:
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
		return dp[n - 1][m - 1] % 1000000007