You are given a matrix grid of n x  m size consisting of values 0 and 1. A value of 1 means that you can enter that cell and 0 implies that entry to that cell is not allowed. 
You start at the upper-left corner of the grid (1, 1) and you have to reach the bottom-right corner (n, m) such that you can only move in the right or down direction from every cell. 
Your task is to calculate the total number of ways of reaching the target modulo (10^{9}+7).
Note: The first (1, 1) and last cell (n, m) of the grid can also be 0
Example 1:
Input:
n = 3, m = 3
grid[][] = {{1, 1, 1};
            {1, 0, 1};
            {1, 1, 1}}
Output:
2
Explanation:
1 1 1
1 0 1
1 1 1
This is one possible path.
1 1 1
1 0 1
1 1 1
This is another possible path.
Example 2:
Input:
n = 1, m = 3
grid = {{1, 0, 1}}
Output :
0
Explanation:
There is no possible path to reach the end.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function uniquePaths() which takes 2 integers n, and m, and a matrix of size n*m as input and returns the number of unique paths from cell (1,1) to (n,m) modulo (10^{9}+7)
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)
Constraints:
1 ≤ n*m ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

    def uniquePaths(self, n, m, grid):

        # code here 

Solutions:
class Solution:

	def uniquePaths(self, n, m, grid):
		dp = grid
		for i in range(n):
			for j in range(m):
				if i == 0 and j == 0:
					continue
				if grid[i][j] == 0:
					continue
				else:
					up = 0
					down = 0
					if i > 0:
						up = dp[i - 1][j]
					if j > 0:
						down = dp[i][j - 1]
					dp[i][j] = up + down
		return dp[-1][-1] % (10 ** 9 + 7)


class Solution:

	def uniquePaths(self, n, m, grid):

		def fun(i, j, dp):
			if i >= 0 and j >= 0 and (grid[i][j] == 0):
				return 0
			if i == 0 and j == 0:
				return 1
			if i < 0 or j < 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			up = fun(i - 1, j, dp)
			left = fun(i, j - 1, dp)
			dp[i][j] = (up + left) % (10 ** 9 + 7)
			return dp[i][j]
		import sys
		sys.setrecursionlimit(10 ** 9)
		dp = [[-1 for i in range(m)] for j in range(n)]
		ans = fun(n - 1, m - 1, dp)
		return ans


class Solution:

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


class Solution:

	def uniquePaths(self, m, n, grid):

		def dfs(i, j, m, n, grid, dp):
			if grid[i][j] != 0:
				dp[0][0] = 1
			for i in range(m):
				for j in range(n):
					if i == 0 and j == 0:
						continue
					elif i - 1 >= 0 and j - 1 >= 0 and (grid[i][j] != 0):
						dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % (10 ** 9 + 7)
					elif j - 1 >= 0 and grid[i][j] != 0:
						dp[i][j] = dp[i][j - 1] % (10 ** 9 + 7)
					elif i - 1 >= 0 and grid[i][j] != 0:
						dp[i][j] = dp[i - 1][j] % (10 ** 9 + 7)
			return dp[-1][-1] % (10 ** 9 + 7)
		dp = []
		if grid[m - 1][n - 1] == 0:
			return 0
		for i in range(m):
			dp.append([0] * n)
		return dfs(0, 0, m, n, grid, dp) % (10 ** 9 + 7)


class Solution:

	def uniquePaths(self, n, m, grid):
		import sys
		sys.setrecursionlimit(10 ** 9)
		dp = [[0 for j in range(m)] for i in range(n)]
		if grid[0][0] == 0 or grid[n - 1][m - 1] == 0:
			return 0
		dp[0][0] = 1
		for i in range(0, n):
			for j in range(0, m):
				if i == 0 and j == 0:
					continue
				if grid[i][j] == 0:
					dp[i][j] = 0
				else:
					left = 0
					up = 0
					if j > 0:
						left = dp[i][j - 1]
					if i > 0:
						up = dp[i - 1][j]
					dp[i][j] = (left + up) % (10 ** 9 + 7)
		return dp[n - 1][m - 1]

	def solve(self, i, j, grid, dp):
		if i == 0 and j == 0:
			dp[i][j] = 1
			return 1
		if i < 0 or j < 0:
			return 0
		if grid[i][j] == 0:
			dp[i][j] = 0
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		left = self.solve(i, j - 1, grid, dp)
		right = self.solve(i - 1, j, grid, dp)
		dp[i][j] = (left + right) % (10 ** 9 + 7)
		return (left + right) % (10 ** 9 + 7)


def dynamic(n, m, grid):
	if grid[0][0] == 0:
		return 0
	dp = [[0 for _ in range(m)] for _ in range(n)]
	for i in range(n):
		if grid[i][0] == 0:
			ti = i
			while ti < n:
				grid[ti][0] = 0
				ti += 1
			break
		else:
			dp[i][0] = 1
	for j in range(m):
		if grid[0][j] == 0:
			tj = j
			while tj < m:
				grid[0][tj] = 0
				tj += 1
			break
		else:
			dp[0][j] = 1
	for i in range(1, n):
		for j in range(1, m):
			if grid[i][j]:
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
	return dp[n - 1][m - 1]

class Solution:

	def uniquePaths(self, n, m, grid):
		return dynamic(n, m, grid) % (10 ** 9 + 7)


class Solution:

	def uniquePaths(self, n, m, grid):
		if grid[0][0] == 0 or grid[n - 1][m - 1] == 0:
			return 0
		ans = [[0 for _ in range(m)] for _ in range(n)]
		ans[0][0] = 1
		for r in range(n):
			for c in range(m):
				if not (r == 0 and c == 0):
					if c == 0:
						left = 0
					else:
						left = ans[r][c - 1]
					if r == 0:
						up = 0
					else:
						up = ans[r - 1][c]
					if grid[r][c] == 0:
						ans[r][c] = 0
					else:
						ans[r][c] = (left + up) % (10 ** 9 + 7)
		return ans[n - 1][m - 1]


class Solution:
	mod = 10 ** 9 + 7

	def uniquePaths(self, n, m, grid):
		dp = [[0] * m for _ in range(n)]
		for j in range(m):
			if grid[0][j] == 0:
				break
			dp[0][j] = 1
		for i in range(n):
			if grid[i][0] == 0:
				break
			dp[i][0] = 1
		for i in range(1, n):
			for j in range(1, m):
				if grid[i][j] == 1:
					dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % self.mod
		return dp[n - 1][m - 1] % self.mod


from collections import deque

class Solution:

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


from collections import deque

class Solution:

	def uniquePaths(self, n, m, grid):
		mod = 1000000007
		if grid[0][0] == 0 or grid[n - 1][m - 1] == 0:
			return 0
		mat = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 0:
					mat[i][j] = 0
				elif i == 0 and j == 0:
					mat[i][j] = 1
				else:
					up = 0
					left = 0
					if i > 0:
						up = mat[i - 1][j]
					if j > 0:
						left = mat[i][j - 1]
					mat[i][j] = (up + left) % mod
		return mat[n - 1][m - 1]


class Solution:

	def uniquePaths(self, n, m, grid):
		if grid[0][0] == 0 or grid[n - 1][m - 1] == 0:
			return 0
		path = [[0] * m for _ in range(n)]
		path[0][0] = 1
		for r in range(n):
			for c in range(m):
				if grid[r][c] == 0:
					continue
				if r - 1 >= 0:
					path[r][c] += path[r - 1][c]
				if c - 1 >= 0:
					path[r][c] += path[r][c - 1]
		return path[n - 1][m - 1] % (10 ** 9 + 7)


class Solution:

	def uniquePaths(self, n, m, grid):
		mod = 10 ** 9 + 7
		if grid[0][0] == 0 or grid[n - 1][m - 1] == 0:
			return 0
		for i in range(n):
			for j in range(m):
				if grid[i][j]:
					if i > 0 and j > 0:
						grid[i][j] = (grid[i - 1][j] + grid[i][j - 1]) % mod
					if j == 0 and i > 0:
						grid[i][j] = grid[i - 1][j]
					if i == 0 and j > 0:
						grid[i][j] = grid[i][j - 1]
		return grid[n - 1][m - 1]


class Solution:

	def fun(self, i, j, grid, dp):
		if i == 0 and j == 0:
			return 1
		elif i < 0 or j < 0:
			return 0
		elif i >= 0 and j >= 0 and (grid[i][j] == 0):
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		up = self.fun(i - 1, j, grid, dp)
		left = self.fun(i, j - 1, grid, dp)
		dp[i][j] = (up + left) % (10 ** 9 + 7)
		return dp[i][j]

	def uniquePaths(self, n, m, grid):
		if grid[0][0] == 0 or grid[n - 1][m - 1] == 0:
			return 0
		dp = [[-1 for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				if i == 0 and j == 0:
					dp[i][j] = 1
				elif grid[i][j] == 0:
					dp[i][j] = 0
				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) % (10 ** 9 + 7)
		return dp[n - 1][m - 1]


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

class Solution:

	def uniquePaths(self, n, m, grid):
		dp = [0] * (m + 1)
		dp[m - 1] = 1
		for i in range(n - 1, -1, -1):
			cur = [0] * (m + 1)
			for j in range(m - 1, -1, -1):
				if grid[i][j] == 0:
					cur[j] = 0
				else:
					cur[j] = dp[j] + cur[j + 1]
			dp = cur
		return dp[0] % mod


mod = 1000000007

class Solution:

	def uniquePaths(self, n, m, grid):
		path = [[0 for x in range(m)] for y in range(n)]
		queue = [(0, 0)]
		if grid[0][0] == 1:
			path[0][0] = 1
		for i in range(1, n):
			if grid[i][0] == 1:
				path[i][0] = path[i - 1][0]
		for i in range(1, m):
			if grid[0][i] == 1:
				path[0][i] = path[0][i - 1]
		for i in range(1, n):
			for j in range(1, m):
				if grid[i][j] == 1:
					path[i][j] = (path[i - 1][j] + path[i][j - 1]) % mod
		return int(path[n - 1][m - 1] % mod)


class Solution:

	def uniquePaths(self, n, m, grid):
		for i in range(1, n):
			if grid[i][0] == 1:
				grid[i][0] = grid[i - 1][0]
		for i in range(1, m):
			if grid[0][i] == 1:
				grid[0][i] = grid[0][i - 1]
		for i in range(1, n):
			for j in range(1, m):
				if grid[i][j] == 1:
					a = b = 0
					if i - 1 > -1:
						a = grid[i - 1][j]
					if j - 1 > -1:
						b = grid[i][j - 1]
					grid[i][j] = a + b
					grid[i][j] %= 10 ** 9 + 7
		return grid[n - 1][m - 1]


from collections import deque

class Solution:

	def uniquePaths(self, n, m, grid):
		if grid[n - 1][m - 1] == 0 or grid[0][0] == 0:
			return 0
		mod = 1000000007
		queue = deque([(0, 0)])
		res = [[0 for j in range(m)] for i in range(n)]
		res[0][0] = 1
		while len(queue) > 0:
			(i, j) = queue.popleft()
			if i + 1 < n:
				res[i + 1][j] = (res[i + 1][j] % mod + res[i][j] % mod) % mod
				if grid[i + 1][j] != 0:
					queue.append((i + 1, j))
					grid[i + 1][j] = 0
			if j + 1 < m:
				res[i][j + 1] = (res[i][j + 1] % mod + res[i][j] % mod) % mod
				if grid[i][j + 1] != 0:
					queue.append((i, j + 1))
					grid[i][j + 1] = 0
		return res[n - 1][m - 1]


import sys
sys.setrecursionlimit(100000000)
from collections import defaultdict
from functools import lru_cache

class Solution:

	def uniquePaths(self, n, m, arr):
		mod = 10 ** 9 + 7
		vis = [[-1 for i in range(m + 1)] for j in range(n + 1)]
		if arr[-1][-1] == 0:
			return 0

		def helper(i, j):
			if i >= n or j >= m or i < 0 or (j < 0):
				return 0
			if vis[i][j] != -1:
				return vis[i][j]
			if arr[i][j] == 0:
				return 0
			if i == n - 1 and j == m - 1:
				return 1
			ans = 0
			if i + 1 < n and vis[i + 1][j] != -1:
				ans += vis[i + 1][j]
			elif i + 1 < n:
				vis[i + 1][j] = helper(i + 1, j) % mod
				ans += vis[i + 1][j]
			if j + 1 < m and vis[i][j + 1] != -1:
				ans += vis[i][j + 1]
			elif j + 1 < m:
				vis[i][j + 1] = helper(i, j + 1) % mod
				ans += vis[i][j + 1]
			vis[i][j] = ans % mod
			return ans % mod
		return helper(0, 0) % mod


import sys
sys.setrecursionlimit(100000000)

class Solution:

	def uniquePaths(self, n, m, a):
		if a[0][0] == 0 or a[n - 1][m - 1] == 0:
			return 0
		t = [[-1 for i in range(m)] for j in range(n)]
		return self.solve(0, 0, n, m, a, t) % (1000000000 + 7)

	def solve(self, i, j, n, m, a, t):
		if i == n - 1 and j == m - 1:
			return 1
		if i >= n or j >= m:
			return 0
		if t[i][j] != -1:
			return t[i][j]
		count = 0
		mod = 1000000000 + 7
		if i + 1 < n and a[i + 1][j] == 1:
			count += self.solve(i + 1, j, n, m, a, t) % mod
		if j + 1 < m and a[i][j + 1] == 1:
			count += self.solve(i, j + 1, n, m, a, t) % mod
		t[i][j] = count % mod
		return t[i][j]


from sys import setrecursionlimit
setrecursionlimit(1000000)

class Solution:

	def getPossibleWays(self, n, m, dp, grid):
		mod = 10 ** 9 + 7
		if n == 0 and m == 0:
			return 1
		if n < 0 or m < 0:
			return 0
		if grid[n][m] == 0:
			return 0
		if dp[n][m] != -1:
			return dp[n][m]
		up = self.getPossibleWays(n - 1, m, dp, grid)
		left = self.getPossibleWays(n, m - 1, dp, grid)
		dp[n][m] = (up + left) % mod
		return dp[n][m]

	def uniquePaths(self, n, m, grid):
		mod = 10 ** 9 + 7
		if grid[0][0] == 0 or grid[n - 1][m - 1] == 0:
			return 0
		dp = [[-1 for i in range(m)] for j in range(n)]
		return self.getPossibleWays(n - 1, m - 1, dp, grid)


class Solution:

	def uniquePaths(self, n, m, d):
		x = 10 ** 9 + 7
		for i in range(1, n):
			if d[i][0] == 1:
				d[i][0] = d[i - 1][0]
		for i in range(1, m):
			if d[0][i] == 1:
				d[0][i] = d[0][i - 1]
		for i in range(1, n):
			for j in range(1, m):
				if d[i][j]:
					if d[i][j - 1] > 0 or d[i - 1][j] > 0:
						d[i][j] = (d[i - 1][j] + d[i][j - 1]) % x
					else:
						d[i][j] = 0
		return d[n - 1][m - 1] % x


class Solution:

	def uniquePaths(self, n, m, grid):
		mod = 1000000007
		paths = [[0] * m for i in range(n)]
		if grid[0][0] == 1:
			paths[0][0] = 1
		for i in range(1, n):
			if grid[i][0] == 1:
				paths[i][0] = paths[i - 1][0]
		for j in range(1, m):
			if grid[0][j] == 1:
				paths[0][j] = paths[0][j - 1]
		for i in range(1, n):
			for j in range(1, m):
				if grid[i][j] == 1:
					paths[i][j] = (paths[i - 1][j] + paths[i][j - 1]) % mod
		return paths[-1][-1]


class Solution:

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


class Solution:

	def uniquePaths(self, n, m, grid):
		if not grid[0][0] or not grid[n - 1][m - 1]:
			return 0
		temp = [[0] * m for _ in range(n)]
		temp[n - 1][m - 1] = 1
		for i in range(n - 2, -1, -1):
			if grid[i][m - 1]:
				temp[i][m - 1] = temp[i + 1][m - 1]
		for i in range(m - 2, -1, -1):
			if grid[n - 1][i]:
				temp[n - 1][i] = temp[n - 1][i + 1]
		for i in range(n - 2, -1, -1):
			for j in range(m - 2, -1, -1):
				if grid[i][j]:
					temp[i][j] = temp[i + 1][j] + temp[i][j + 1]
		return temp[0][0] % int(1000000000.0 + 7)


class Solution:

	def uniquePaths(self, n, m, grid):
		dp = [[0 for _ in range(m)] for _ in range(n)]
		if grid[0][0] == 0:
			return 0
		else:
			for row in range(n):
				for col in range(m):
					if row == 0 and col == 0:
						dp[row][col] = 1
					elif row == 0 and grid[row][col] != 0:
						dp[row][col] = dp[row][col - 1]
					elif col == 0 and grid[row][col] != 0:
						dp[row][col] = dp[row - 1][col]
					elif grid[row][col] != 0:
						dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
			return dp[n - 1][m - 1] % 1000000007


class Solution:

	def uniquePaths(self, n, m, grid):
		ss = False
		for i in range(n):
			if grid[i][0] == 0:
				ss = True
			if ss:
				grid[i][0] = 0
		ss = False
		for i in range(m):
			if grid[0][i] == 0:
				ss = True
			if ss:
				grid[0][i] = 0
		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[-1][-1] % (pow(10, 9) + 7)


mod = 1000000007

class Solution:

	def uniquePaths(self, n, m, grid):
		memo = []
		for i in range(n):
			memo.append([])
			for j in range(m):
				memo[i].append(0)
		for i in range(n):
			if i == 0 and grid[i][0] == 1:
				memo[i][0] = 1
			elif grid[i][0] == 0:
				memo[i][0] = 0
			else:
				memo[i][0] = memo[i - 1][0] % mod
		for j in range(m):
			if j == 0 and grid[0][j] == 1:
				memo[0][j] = 1
			elif grid[0][j] == 0:
				memo[0][j] = 0
			else:
				memo[0][j] = memo[0][j - 1] % mod
		for i in range(1, n):
			for j in range(1, m):
				if grid[i][j] == 0:
					memo[i][j] = 0
				else:
					memo[i][j] = (memo[i - 1][j] + memo[i][j - 1]) % mod
		return memo[n - 1][m - 1]


class Solution:

	def uniquePaths(self, n, m, grid):
		if grid[0][0] == 0 or grid[n - 1][m - 1] == 0:
			return 0
		vss = [0] * m
		vss[0] = 1
		for r in range(n):
			vss[0] = 0 if grid[r][0] == 0 else vss[0]
			for c in range(1, m):
				if grid[r][c]:
					vss[c] += vss[c - 1]
				else:
					vss[c] = 0
		return vss[m - 1] % (10 ** 9 + 7)


class Solution:

	def uniquePaths(self, r, c, grid):
		mod = 1000000007
		paths = [[0] * c for i in range(r)]
		if grid[0][0] == 1:
			paths[0][0] = 1
		for j in range(1, c):
			if grid[0][j] == 1:
				paths[0][j] = paths[0][j - 1]
		for i in range(1, r):
			if grid[i][0] == 1:
				paths[i][0] = paths[i - 1][0]
		for i in range(1, r):
			for j in range(1, c):
				if grid[i][j] == 1:
					paths[i][j] = (paths[i - 1][j] + paths[i][j - 1]) % mod
		return paths[-1][-1]


from collections import deque

class Solution:

	def uniquePaths(self, n, m, grid):
		dp = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			if grid[i][0] == 1:
				dp[i][0] = 1
			else:
				break
		for j in range(m):
			if grid[0][j] == 1:
				dp[0][j] = 1
			else:
				break
		for i in range(1, n):
			for j in range(1, m):
				if grid[i][j] == 1:
					dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
		return dp[n - 1][m - 1]


class Solution:

	def uniquePaths(self, n, m, grid):
		if grid[0][0] == 0 or grid[n - 1][m - 1] == 0:
			return 0
		if n < m:
			return self.uniquePaths(m, n, list(zip(*grid)))
		dp = [0 for _ in range(m)]
		dp[0] = 1
		mod = 1000000000 + 7
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 0:
					dp[j] = 0
				elif j > 0:
					dp[j] += dp[j - 1]
					dp[j] %= mod
		return dp[m - 1]


class Solution:

	def uniquePaths(self, r, c, mat):
		mod = 1000000007
		ans = [[0] * c] * r
		for i in range(r):
			for j in range(c):
				if mat[i][j] == 0:
					ans[i][j] = 0
				elif i == 0 and j == 0:
					ans[i][j] = 1
				elif i == 0:
					ans[i][j] = ans[i][j - 1]
				elif j == 0:
					ans[i][j] = ans[i - 1][j]
				else:
					ans[i][j] = ans[i - 1][j] % mod + ans[i][j - 1] % mod
		return ans[-1][-1] % mod
		return mat


class Solution:

	def uniquePaths(self, n, m, grid):
		if not grid[0][0]:
			return 0
		result = [[0] * m for _ in range(n)]
		for row in range(n):
			result[row][0] = grid[row][0]
			if not grid[row][0]:
				break
		for col in range(m):
			result[0][col] = grid[0][col]
			if not grid[0][col]:
				break
		for row in range(1, n):
			for col in range(1, m):
				if grid[row][col]:
					result[row][col] += result[row - 1][col] + result[row][col - 1]
		return result[-1][-1] % (10 ** 9 + 7)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def uniquePaths(self, n, m, g):
		mod = 10 ** 9 + 7

		def f(i, j):
			if g[0][0] == 0:
				return 0
			if i == 0 and j == 0:
				return 1
			if i < 0 or j < 0 or g[i][j] == 0:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			l = f(i - 1, j)
			r = f(i, j - 1)
			dp[i][j] = l + r % mod
			return dp[i][j]
		dp = [[-1] * m for i in range(n)]
		return f(n - 1, m - 1) % mod


class Solution:

	def uniquePaths(self, n, m, grid):
		prev = [0] * m
		curr = [0] * m
		mod = 10 ** 9 + 7
		for i in range(n):
			for j in range(m):
				if i == 0 and j == 0 and (grid[i][j] == 1):
					curr[j] = 1
				else:
					up = 0
					left = 0
					if i > 0 and grid[i][j] == 1:
						up = prev[j]
					if j > 0 and grid[i][j] == 1:
						left = curr[j - 1]
					curr[j] = (up + left) % mod
			prev = curr
		return prev[m - 1]