You have got a maze, which is a n*n Grid. Every cell of the maze contains these numbers 1, 2 or 3. 
If it contains 1 : means we can go Right from that cell only.
If it contains 2 : means we can go Down from that cell only.
If it contains 3 : means we can go Right and Down to both paths from that cell.
We cant go out of the maze at any time.
Initially, You are on the Top Left Corner of The maze(Entry). And, You need to go to the Bottom Right Corner of the Maze(Exit).
You need to find the total number of paths from Entry to Exit Point.
There may be many paths but you need to select that path which contains the maximum number of Adventure.
The Adventure on a path is calculated by taking the sum of all the cell values thatlies in the path.
 
Example 1:
Input: matrix = {{1,1,3,2,1},{3,2,2,1,2},
{1,3,3,1,3},{1,2,3,1,2},{1,1,1,3,1}}
Output: {4,18}
Explanation: There are total 4 Paths Available 
out of which The Max Adventure is 18. Total 
possible Adventures are 18,17,17,16. Of these 
18 is the maximum.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function FindWays() which takes matrix as input parameter and returns a list containg total number of ways to reach at (n, n) modulo 10^{9} + 7 and maximum number of Adventure.
 
Expected Time Complexity: O(n^{2})
Expected Space Complexity: O(n^{2})
 
Constraints:
1 <= n <= 100

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Matrices

Dynamic programming

Data structures

Starter code: #User function Template for python3



class Solution:

	def FindWays(self, matrix):

		# Code here

Solutions:
class Solution:

	def FindWays(self, matrix):
		m = len(matrix[0])
		n = len(matrix)
		dp = [[[-1, 0] for i in range(m)] for j in range(n)]
		dp[0][0][0] = 1
		dp[0][0][1] = matrix[0][0]
		for i in range(1, m):
			if (matrix[0][i - 1] == 1 or matrix[0][i - 1] == 3) and dp[0][i - 1][0] != -1:
				dp[0][i][0] = dp[0][i - 1][0]
				dp[0][i][1] = dp[0][i - 1][1] + matrix[0][i]
		for j in range(1, n):
			if (matrix[j - 1][0] == 2 or matrix[j - 1][0] == 3) and dp[j - 1][0][0] != -1:
				dp[j][0][0] = dp[j - 1][0][0]
				dp[j][0][1] = dp[j - 1][0][1] + matrix[j][0]
		for i in range(1, n):
			for j in range(1, m):
				if (matrix[i - 1][j] == 2 or matrix[i - 1][j] == 3) and dp[i - 1][j][0] != -1:
					dp[i][j][0] = dp[i - 1][j][0]
					dp[i][j][1] = dp[i - 1][j][1] + matrix[i][j]
				if (matrix[i][j - 1] == 1 or matrix[i][j - 1] == 3) and dp[i][j - 1][0] != -1:
					dp[i][j][0] = max(dp[i][j][0], 0)
					dp[i][j][0] += dp[i][j - 1][0]
					dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][1] + matrix[i][j])
		dp[n - 1][m - 1][0] = max(dp[n - 1][m - 1][0], 0)
		dp[n - 1][m - 1][0] = dp[n - 1][m - 1][0] % int(1000000000.0 + 7)
		return dp[n - 1][m - 1]


class Solution:

	def FindWays(self, matrix):
		n = len(matrix)
		mod = 10 ** 9 + 7
		matrix[0][0] = (matrix[0][0], 1, matrix[0][0])
		for i in range(n - 1):
			if matrix[0][i][0] == 1 or matrix[0][i][0] == 3:
				matrix[0][i + 1] = (matrix[0][i + 1], matrix[0][i][1], matrix[0][i + 1] + matrix[0][i][2])
			else:
				matrix[0][i + 1] = (0, 0, 0)
			if matrix[i][0][0] == 2 or matrix[i][0][0] == 3:
				matrix[i + 1][0] = (matrix[i + 1][0], matrix[i][0][1], matrix[i + 1][0] + matrix[i][0][2])
			else:
				matrix[i + 1][0] = (0, 0, 0)
		for i in range(1, n):
			for j in range(1, n):
				value = matrix[i][j]
				count = 0
				summa = 0
				if matrix[i - 1][j][0] == 2 or matrix[i - 1][j][0] == 3:
					count += matrix[i - 1][j][1]
					summa = matrix[i - 1][j][2]
				if matrix[i][j - 1][0] == 1 or matrix[i][j - 1][0] == 3:
					count += matrix[i][j - 1][1]
					summa = max(summa, matrix[i][j - 1][2])
				if count:
					matrix[i][j] = (value, count % mod, (summa + value) % mod)
				else:
					matrix[i][j] = (0, 0, 0)
		return (matrix[n - 1][n - 1][1], matrix[n - 1][n - 1][2]) if matrix[n - 1][n - 1][1] else (0, 0)


from itertools import product
MOD = int(1000000000.0 + 7)

class Solution:

	def FindWays(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		dp = [[(0, 0) for _ in range(n)] for __ in range(m)]
		dp[0][0] = (1, matrix[0][0])
		for i in range(1, m):
			if matrix[i - 1][0] == 1:
				break
			val = dp[i - 1][0][1]
			dp[i][0] = (1, val + matrix[i][0])
		for j in range(1, n):
			if matrix[0][j - 1] == 2:
				break
			val = dp[0][j - 1][1]
			dp[0][j] = (1, val + matrix[0][j])
		for (i, j) in product(range(1, m), range(1, n)):
			(cnt_top, val_top) = dp[i - 1][j]
			(cnt_left, val_left) = dp[i][j - 1]
			(cnt, val) = (0, 0)
			if matrix[i - 1][j] != 1 and cnt_top:
				cnt = cnt_top % MOD
				val = val_top + matrix[i][j]
			if matrix[i][j - 1] != 2 and cnt_left:
				cnt = (cnt + cnt_left) % MOD
				val = max(val, val_left + matrix[i][j])
			dp[i][j] = (cnt, val)
		return list(dp[m - 1][n - 1])


class Solution:

	def FindWays(self, matrix):
		n = len(matrix)
		dp = [[(0, matrix[i][j]) for j in range(n)] for i in range(n)]
		mod = 10 ** 9 + 7
		dp[0][0] = (1, matrix[0][0])
		for i in range(n):
			for j in range(n):
				if i - 1 >= 0 and (matrix[i - 1][j] == 3 or matrix[i - 1][j] == 2):
					if dp[i - 1][j][0] > 0:
						dp[i][j] = (dp[i - 1][j][0] % mod, dp[i - 1][j][1] + dp[i][j][1])
				if j - 1 >= 0 and (matrix[i][j - 1] == 3 or matrix[i][j - 1] == 1):
					first = (dp[i][j][0] + dp[i][j - 1][0]) % mod
					sec = dp[i][j][1]
					if dp[i][j - 1][0] > 0:
						sec = max(dp[i][j - 1][1] + matrix[i][j], dp[i][j][1]) % mod
					dp[i][j] = (first, sec)
		ans = []
		last = dp[n - 1][n - 1]
		ans.append(last[0] % mod)
		if last[0] > 0:
			ans.append(last[1])
		else:
			ans.append(0)
		return ans


class Solution:

	def FindWays(self, matrix):
		dp = dict()

		def rec(ro, co, n, m):
			if ro == n - 1 and co == m - 1:
				return 1
			if (ro, co) not in dp:
				ans = 0
				if matrix[ro][co] in [1, 3]:
					if co + 1 < m:
						ans += rec(ro, co + 1, n, m)
				if matrix[ro][co] in [2, 3]:
					if ro + 1 < n:
						ans += rec(ro + 1, co, n, m)
				dp[ro, co] = ans % (10 ** 9 + 7)
			return dp[ro, co]
		op = rec(0, 0, len(matrix), len(matrix[0]))
		if op == 0:
			return [0, 0]
		dp = dict()

		def rec2(ro, co, n, m):
			if ro == n - 1 and co == m - 1:
				return matrix[-1][-1]
			if (ro, co) not in dp:
				ans = -1000000000000.0
				if matrix[ro][co] in [1, 3]:
					if co + 1 < m:
						ans = max(ans, matrix[ro][co] + rec2(ro, co + 1, n, m))
				if matrix[ro][co] in [2, 3]:
					if ro + 1 < n:
						ans = max(ans, matrix[ro][co] + rec2(ro + 1, co, n, m))
				dp[ro, co] = ans
			return dp[ro, co]
		return [op, rec2(0, 0, len(matrix), len(matrix[0])) % (10 ** 9 + 7)]


class Solution:

	def FindWays(self, matrix):
		n = len(matrix)
		mod = 10 ** 9 + 7

		def f(i, j, dp):
			if i < 0 or i >= n or j < 0 or (j >= n):
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			if i == n - 1 and j == n - 1:
				return 1
			if matrix[i][j] == 1:
				dp[i][j] = f(i, j + 1, dp) % mod
				return dp[i][j]
			elif matrix[i][j] == 2:
				dp[i][j] = f(i + 1, j, dp) % mod
				return dp[i][j]
			else:
				dp[i][j] = (f(i, j + 1, dp) + f(i + 1, j, dp)) % mod
				return dp[i][j]

		def ff(i, j, pdp):
			if i < 0 or i >= n or j < 0 or (j >= n):
				return -1000000000
			if pdp[i][j] != -1:
				return pdp[i][j]
			if i == n - 1 and j == n - 1:
				return matrix[i][j]
			if matrix[i][j] == 1:
				pdp[i][j] = ff(i, j + 1, pdp) + 1
				return pdp[i][j]
			elif matrix[i][j] == 2:
				pdp[i][j] = ff(i + 1, j, pdp) + 2
				return pdp[i][j]
			else:
				pdp[i][j] = max(ff(i, j + 1, pdp), ff(i + 1, j, pdp)) + 3
				return pdp[i][j]
		ans = [0]
		point = [0]
		dp = [[-1] * n for i in range(n)]
		pdp = [[-1] * n for i in range(n)]
		fin = f(0, 0, dp)
		fin2 = ff(0, 0, pdp)
		if fin == 0:
			return [0, 0]
		return [fin, fin2]


MOD = int(1000000000.0 + 7)

def f(A, x, y, N, dp, adv):
	if x == N - 1 and y == N - 1:
		adv[x][y] = A[x][y]
		return 1
	if x < 0 or x >= N or y < 0 or (y >= N):
		return 0
	if dp[x][y] != -1:
		return dp[x][y]
	ans = 0
	if A[x][y] == 1:
		out = f(A, x, y + 1, N, dp, adv)
		if y + 1 < N and adv[x][y + 1] > 0:
			adv[x][y] = max(adv[x][y], A[x][y] + adv[x][y + 1])
	elif A[x][y] == 2:
		out = f(A, x + 1, y, N, dp, adv)
		if x + 1 < N and adv[x + 1][y] > 0:
			adv[x][y] = max(adv[x][y], A[x][y] + adv[x + 1][y])
	else:
		r = f(A, x, y + 1, N, dp, adv)
		d = f(A, x + 1, y, N, dp, adv)
		if y + 1 < N and adv[x][y + 1] > 0:
			adv[x][y] = max(adv[x][y], A[x][y] + adv[x][y + 1])
		if x + 1 < N and adv[x + 1][y] > 0:
			adv[x][y] = max(adv[x][y], A[x][y] + adv[x + 1][y])
		out = r + d
	ans = out
	ans %= MOD
	dp[x][y] = ans
	return ans

class Solution:

	def FindWays(self, A):
		N = len(A)
		dp = [[-1 for i in range(N)] for i in range(N)]
		adv = [[0 for i in range(N)] for i in range(N)]
		ans = f(A, 0, 0, N, dp, adv)
		return [ans, adv[0][0]]


class Solution:

	def FindWays(self, matrix):
		(m, n) = (len(matrix), len(matrix[0]))
		dp = [[0] * n for _ in range(m)]
		M = 1000000007
		for i in range(m):
			for j in range(n):
				num = 1 if (i, j) == (0, 0) else 0
				value = 0
				if i > 0 and matrix[i - 1][j] in [2, 3]:
					value = max(value, dp[i - 1][j][1])
					num += dp[i - 1][j][0]
				if j > 0 and matrix[i][j - 1] in [1, 3]:
					value = max(value, dp[i][j - 1][1])
					num += dp[i][j - 1][0]
				if value == 0 and (i, j) != (0, 0):
					dp[i][j] = (num, 0)
				else:
					dp[i][j] = (num % M, (value + matrix[i][j]) % M)
		return dp[m - 1][n - 1]


from math import inf

class Solution:

	def FindWays(self, x):
		dp = {}

		def f(i, j):
			if i == j == n - 1:
				return [x[i][j], 1]
			if (i, j) in dp:
				return list(dp[i, j])
			ans = [-inf, 0]
			if x[i][j] == 3:
				if i < n - 1:
					a = f(i + 1, j)
					ans[1] += a[1]
					ans[0] = max(a[0], ans[0])
				if j < n - 1:
					a = f(i, j + 1)
					ans[1] += a[1]
					ans[0] = max(a[0], ans[0])
			elif x[i][j] == 2:
				if i < n - 1:
					a = f(i + 1, j)
					ans[1] += a[1]
					ans[0] = max(a[0], ans[0])
			elif j < n - 1:
				a = f(i, j + 1)
				ans[1] += a[1]
				ans[0] = max(a[0], ans[0])
			dp[i, j] = (ans[0] + x[i][j], ans[1])
			return list(dp[i, j])
		n = len(x)
		a = f(0, 0)
		if a[0] == -inf:
			return [0, 0]
		a[1] = a[1] % (10 ** 9 + 7)
		return a[::-1]


class Solution:

	def FindWays(self, mat):
		(m, n) = (len(mat), len(mat[0]))
		dp = [[0 for i in range(n)] for j in range(m)]
		for i in range(m - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				if i == m - 1 and j == n - 1:
					dp[i][j] = 1
				elif i == m - 1:
					if mat[i][j] != 2:
						dp[i][j] = dp[i][j + 1]
					if dp[i][j]:
						mat[i][j] += mat[i][j + 1]
					else:
						mat[i][j] = 0
				elif j == n - 1:
					if mat[i][j] != 1:
						dp[i][j] = dp[i + 1][j]
					if dp[i][j]:
						mat[i][j] += mat[i + 1][j]
					else:
						mat[i][j] = 0
				elif mat[i][j] == 1:
					dp[i][j] = dp[i][j + 1]
					if dp[i][j]:
						mat[i][j] += mat[i][j + 1]
					else:
						mat[i][j] = 0
				elif mat[i][j] == 2:
					dp[i][j] = dp[i + 1][j]
					if dp[i][j]:
						mat[i][j] += mat[i + 1][j]
					else:
						mat[i][j] = 0
				else:
					dp[i][j] = dp[i][j + 1] + dp[i + 1][j]
					if dp[i][j]:
						mat[i][j] += max(mat[i + 1][j], mat[i][j + 1])
					else:
						mat[i][j] = 0
				dp[i][j] = dp[i][j] % (10 ** 9 + 7)
		return [dp[0][0], mat[0][0]]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		matrix = []
		for _ in range(n):
			cur = list(map(int, input().split()))
			matrix.append(cur)
		obj = Solution()
		ans = obj.FindWays(matrix)
		for _ in ans:
			print(_, end=' ')
		print()


class Solution:

	def FindWays(self, l):
		n = len(l)
		m = len(l[0])
		dp = [[0 for _ in range(m)] for _ in range(n)]
		ln = [[0 for _ in range(m)] for _ in range(n)]
		ln[0][0] = l[0][0]
		dp[0][0] = 1
		for i in range(1, n):
			if l[i - 1][0] != 1:
				dp[i][0] = 1
				ln[i][0] = (ln[i - 1][0] + l[i][0]) % 1000000007
			else:
				break
		for j in range(1, m):
			if l[0][j - 1] != 2:
				dp[0][j] = 1
				ln[0][j] = (ln[0][j - 1] + l[0][j]) % 1000000007
			else:
				break
		for i in range(1, n):
			for j in range(1, m):
				if l[i - 1][j] != 1 and ln[i - 1][j] != 0:
					dp[i][j] = dp[i - 1][j] % 1000000007
					ln[i][j] = (ln[i - 1][j] + l[i][j]) % 1000000007
				if l[i][j - 1] != 2 and ln[i][j - 1] != 0:
					dp[i][j] = (dp[i][j - 1] + dp[i][j]) % 1000000007
					ln[i][j] = max(ln[i][j - 1] + l[i][j], ln[i][j]) % 1000000007
		return [dp[-1][-1], ln[-1][-1]]


class Solution:

	def FindWays(self, matrix):
		rows = len(matrix)
		columns = len(matrix[0])
		ways = [[0] * (columns + 1) for _ in range(rows + 1)]
		lengths = [[0] * (columns + 1) for _ in range(rows + 1)]
		matrix2 = [[0] * (columns + 1)]
		matrix2 += [[0] + matrix[r] for r in range(rows)]
		matrix2[0][1] = 2
		ways[0][1] = 1
		for y in range(1, rows + 1):
			for x in range(1, columns + 1):
				if matrix2[y][x - 1] == 1 or matrix2[y][x - 1] == 3:
					ways[y][x] = ways[y][x - 1]
					if ways[y][x - 1]:
						lengths[y][x] = lengths[y][x - 1] + matrix2[y][x]
				if matrix2[y - 1][x] == 2 or matrix2[y - 1][x] == 3:
					ways[y][x] += ways[y - 1][x]
					if ways[y - 1][x]:
						lengths[y][x] = max(lengths[y][x], lengths[y - 1][x] + matrix2[y][x])
		return (ways[-1][-1] % (10 ** 9 + 7), lengths[-1][-1])


class Pair:

	def __init__(self, path, value):
		self.path = path
		self.value = value

class Solution:

	def FindWays(self, matrix):
		n = len(matrix)
		mod = 10 ** 9 + 7
		dp = [[Pair(0, 0) for i in range(n)] for j in range(n)]
		for i in range(n):
			for j in range(n):
				if i == 0 and j == 0:
					dp[i][j].path = 1
					dp[i][j].value = matrix[i][j]
				elif i == 0 and j > 0:
					if matrix[i][j - 1] != 2 and dp[i][j - 1].path != 0:
						dp[i][j].path = dp[i][j - 1].path
						dp[i][j].value = dp[i][j - 1].value + matrix[i][j]
				elif j == 0 and i > 0:
					if matrix[i - 1][j] != 1 and dp[i - 1][j].path != 0:
						dp[i][j].path = dp[i - 1][j].path
						dp[i][j].value = dp[i - 1][j].value + matrix[i][j]
					else:
						continue
				else:
					if matrix[i - 1][j] != 1 and dp[i - 1][j].path != 0:
						dp[i][j].path = dp[i - 1][j].path + dp[i][j].path
						dp[i][j].value = dp[i - 1][j].value + matrix[i][j]
					if matrix[i][j - 1] != 2 and dp[i][j - 1].path != 0:
						dp[i][j].path += dp[i][j - 1].path
						dp[i][j].value = max(dp[i][j].value, dp[i][j - 1].value + matrix[i][j])
		return [dp[n - 1][n - 1].path % mod, dp[n - 1][n - 1].value]


class Solution:

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


def wtf(p):
	return p % 1000000007
(RYTE, DOWN) = (1, 2)

class Solution:

	def FindWays(self, maze):
		n = len(maze)

		def cons():
			return [[0] * n for _ in range(n)]
		adv = cons()
		adv[0][0] = maze[0][0]
		pts = cons()
		pts[0][0] = 1
		for j in range(1, n):
			if maze[0][j - 1] == DOWN:
				break
			adv[0][j] = adv[0][j - 1] + maze[0][j]
			pts[0][j] = 1
		for i in range(1, n):
			if maze[i - 1][0] == RYTE:
				break
			adv[i][0] = adv[i - 1][0] + maze[i][0]
			pts[i][0] = 1
		for i in range(1, n):
			for j in range(1, n):
				if maze[i - 1][j] != RYTE and pts[i - 1][j]:
					adv[i][j] = adv[i - 1][j] + maze[i][j]
					pts[i][j] = pts[i - 1][j]
				if maze[i][j - 1] != DOWN and pts[i][j - 1]:
					adv[i][j] = max(adv[i][j], adv[i][j - 1] + maze[i][j])
					pts[i][j] += pts[i][j - 1]
		if not pts[-1][-1]:
			return (0, 0)
		return (wtf(pts[-1][-1]), adv[-1][-1])


def modulo(p):
	return p % 1000000007
(right, down) = (1, 2)

class Solution:

	def FindWays(self, maze):
		n = len(maze)
		adv = [[0] * n for _ in range(n)]
		adv[0][0] = maze[0][0]
		pts = [[0] * n for _ in range(n)]
		pts[0][0] = 1
		for j in range(1, n):
			if maze[0][j - 1] == down:
				break
			adv[0][j] = adv[0][j - 1] + maze[0][j]
			pts[0][j] = 1
		for i in range(1, n):
			if maze[i - 1][0] == right:
				break
			adv[i][0] = adv[i - 1][0] + maze[i][0]
			pts[i][0] = 1
		for i in range(1, n):
			for j in range(1, n):
				if maze[i - 1][j] != right and pts[i - 1][j]:
					adv[i][j] = adv[i - 1][j] + maze[i][j]
					pts[i][j] = pts[i - 1][j]
				if maze[i][j - 1] != down and pts[i][j - 1]:
					adv[i][j] = max(adv[i][j], adv[i][j - 1] + maze[i][j])
					pts[i][j] += pts[i][j - 1]
		if not pts[-1][-1]:
			return (0, 0)
		return (modulo(pts[-1][-1]), adv[-1][-1])


import math

class Solution:

	def FindWays(self, matrix):

		def f1(i, j, m, dp):
			n = len(m)
			if i == n - 1 and j == n - 1:
				return m[i][j]
			if i >= n or j >= n:
				return -math.inf
			if dp[i][j] != -1:
				return dp[i][j]
			up = left = -1000000007
			if m[i][j] == 3:
				up = 3 + f1(i + 1, j, m, dp)
				left = 3 + f1(i, j + 1, m, dp)
			elif m[i][j] == 2:
				up = 2 + f1(i + 1, j, m, dp)
			else:
				left = 1 + f1(i, j + 1, m, dp)
			dp[i][j] = max(up, left)
			return dp[i][j]

		def f2(i, j, m, dp):
			if i == n - 1 and j == n - 1:
				return 1
			if i >= n or j >= n:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			up = left = 0
			if m[i][j] == 3:
				up = f2(i + 1, j, m, dp)
				left = f2(i, j + 1, m, dp)
			if m[i][j] == 2:
				up = f2(i + 1, j, m, dp)
			if m[i][j] == 1:
				left = f2(i, j + 1, m, dp)
			dp[i][j] = up + left
			return dp[i][j]
		n = len(matrix)
		dp1 = [[-1 for i in range(n)] for j in range(n)]
		dp2 = [[-1 for i in range(n)] for j in range(n)]
		ways = f2(0, 0, matrix, dp1) % 1000000007
		cost = f1(0, 0, matrix, dp2) % 1000000007
		if cost < 0:
			cost = 0
		if ways == 0:
			cost = 0
		return [ways, cost]


class Solution:

	def FindWays(self, matrix):
		dp = [[[0, 0] for _ in range(len(matrix))] for _ in range(len(matrix))]
		dp[0][0] = [1, 0]
		for i in range(len(matrix)):
			for j in range(len(matrix)):
				if i > 0 and matrix[i - 1][j] in (2, 3):
					dp[i][j][0] += dp[i - 1][j][0]
					dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1])
				if j > 0 and matrix[i][j - 1] in (1, 3):
					dp[i][j][0] += dp[i][j - 1][0]
					dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][1])
				if dp[i][j][0] > 0:
					dp[i][j][0] %= 1000000007
					dp[i][j][1] += matrix[i][j]
		return dp[-1][-1]


class Solution:

	def FindWays(self, matrix):
		dp = [[0 for i in range(len(matrix[0]))] for i in range(len(matrix))]
		dp[0][0] = 1
		for i in range(1, len(matrix[0])):
			if (matrix[0][i - 1] == 1 or matrix[0][i - 1] == 3) and dp[0][i - 1] == 1:
				dp[0][i] = 1
		for i in range(1, len(matrix)):
			if (matrix[i - 1][0] == 2 or matrix[i - 1][0] == 3) and dp[i - 1][0] == 1:
				dp[i][0] = 1
		for i in range(1, len(matrix)):
			for j in range(1, len(matrix[0])):
				if matrix[i][j - 1] == 1 or matrix[i][j - 1] == 3:
					dp[i][j] = dp[i][j] + dp[i][j - 1]
				if matrix[i - 1][j] == 2 or matrix[i - 1][j] == 3:
					dp[i][j] = dp[i][j] + dp[i - 1][j]
		l = []
		l.append(dp[len(matrix) - 1][len(matrix[0]) - 1] % (10 ** 9 + 7))
		dp = [[0 for i in range(len(matrix[0]))] for i in range(len(matrix))]
		dp[0][0] = matrix[0][0]
		for i in range(1, len(matrix[0])):
			if (matrix[0][i - 1] == 1 or matrix[0][i - 1] == 3) and dp[0][i - 1] != 0:
				dp[0][i] = dp[0][i] + matrix[0][i] + dp[0][i - 1]
		for i in range(1, len(matrix)):
			if (matrix[i - 1][0] == 2 or matrix[i - 1][0] == 3) and dp[i - 1][0] != 0:
				dp[i][0] = dp[i][0] + matrix[i][0] + dp[i - 1][0]
		for i in range(1, len(matrix)):
			r = 0
			g = 0
			for j in range(1, len(matrix[0])):
				if matrix[i][j - 1] == 1 or matrix[i][j - 1] == 3:
					r = dp[i][j - 1]
				if matrix[i - 1][j] == 2 or matrix[i - 1][j] == 3:
					g = dp[i - 1][j]
				if r != 0 or g != 0:
					dp[i][j] = dp[i][j] + matrix[i][j] + max(r, g)
					r = 0
					g = 0
		l.append(dp[len(matrix) - 1][len(matrix[0]) - 1])
		return l


import sys
sys.setrecursionlimit(3500)

class Solution:

	def FindWays(self, matrix):
		MOD = 10 ** 9 + 7
		self.mat = matrix
		self.n = len(matrix)
		self.m = len(matrix[0])
		self.dp = [[[-1, -1] for _ in range(self.m)] for _ in range(self.n)]

		def dfs(x, y):
			if self.dp[x][y][0] != -1:
				return self.dp[x][y]
			if x == self.n - 1 and y == self.m - 1:
				self.dp[x][y] = [1, self.mat[x][y]]
				return self.dp[x][y]
			elif self.mat[x][y] == 1 and y + 1 < self.m:
				hl = dfs(x, y + 1)
				if hl[0] == 0:
					self.dp[x][y] = [0, 0]
					return self.dp[x][y]
				self.dp[x][y] = [hl[0], hl[1] + self.mat[x][y]]
				return self.dp[x][y]
			elif self.mat[x][y] == 2 and x + 1 < self.n:
				hl = dfs(x + 1, y)
				if hl[0] == 0:
					self.dp[x][y] = [0, 0]
					return self.dp[x][y]
				self.dp[x][y] = [hl[0], self.mat[x][y] + hl[1]]
				return self.dp[x][y]
			elif self.mat[x][y] == 3:
				m1 = m2 = 0
				p1 = p2 = 0
				if y + 1 < self.m:
					hl = dfs(x, y + 1)
					p1 = hl[0]
					m1 = self.mat[x][y] + hl[1]
				if x + 1 < self.n:
					hl = dfs(x + 1, y)
					p2 = hl[0]
					m2 = self.mat[x][y] + hl[1]
				if p1 + p2 == 0:
					self.dp[x][y] = [0, 0]
					return self.dp[x][y]
				self.dp[x][y] = [p1 + p2, max(m1, m2)]
				return self.dp[x][y]
			else:
				self.dp[x][y] = [0, 0]
				return self.dp[x][y]
		ans = dfs(0, 0)
		return [ans[0] % MOD, ans[1] % MOD]


class Solution:

	def FindWays(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		dp = [[0 for i in range(n)] for j in range(m)]
		dp2 = [[-1 for i in range(n)] for j in range(m)]
		dp2[0][0] = 1
		for i in range(1, m):
			if matrix[i - 1][0] == 2 or matrix[i - 1][0] == 3:
				if dp2[i - 1][0] != -1:
					dp2[i][0] = dp2[i - 1][0]
		for j in range(1, n):
			if matrix[0][j - 1] == 1 or matrix[0][j - 1] == 3:
				if dp2[0][j - 1] != -1:
					dp2[0][j] = dp2[0][j - 1]
		for i in range(1, m):
			for j in range(1, n):
				l = 0
				r = 0
				if matrix[i][j - 1] == 1 or matrix[i][j - 1] == 3:
					if dp2[i][j - 1] != -1:
						l = dp2[i][j - 1]
				if matrix[i - 1][j] == 2 or matrix[i - 1][j] == 3:
					if dp2[i - 1][j] != -1:
						r = dp2[i - 1][j]
				if l != 0 or r != 0:
					dp2[i][j] = l + r
		dp[0][0] = matrix[0][0]
		for i in range(1, m):
			l = 0
			if matrix[i - 1][0] == 2 or matrix[i - 1][0] == 3:
				l = dp[i - 1][0]
				if l != 0:
					dp[i][0] = l + matrix[i][0]
		for j in range(1, n):
			l = 0
			if matrix[0][j - 1] == 1 or matrix[0][j - 1] == 3:
				l = dp[0][j - 1]
				if l != 0:
					dp[0][j] = l + matrix[0][j]
		for i in range(1, m):
			for j in range(1, n):
				l = 0
				r = 0
				if matrix[i][j - 1] == 1 or matrix[i][j - 1] == 3:
					l = dp[i][j - 1]
				if matrix[i - 1][j] == 2 or matrix[i - 1][j] == 3:
					r = dp[i - 1][j]
				if l != 0 or r != 0:
					dp[i][j] = max(l, r) + matrix[i][j]
				else:
					dp[i][j] = 0
		if dp2[-1][-1] == -1:
			l = 0
		else:
			l = dp2[-1][-1] % 1000000007
		r = dp[-1][-1]
		return [l, r]


class Solution:

	def FindWays(self, matrix):
		dp = [[[0, 0]] * len(matrix) for _ in range(len(matrix))]
		dp[-1][-1] = [1, matrix[-1][-1]]
		space = range(len(matrix) - 2, -1, -1)
		for j in space:
			if matrix[-1][j] & 1:
				dp[-1][j] = [dp[-1][j + 1][0], matrix[-1][j] + dp[-1][j + 1][1]]
			else:
				dp[-1][j] = [0, 0]
		for i in space:
			if matrix[i][-1] & 2:
				dp[i][-1] = [dp[i + 1][-1][0], matrix[i][-1] + dp[i + 1][-1][1]]
			else:
				dp[i][-1] = [0, 0]
		for i in space:
			for j in space:
				(r_path, r_val, d_path, d_val) = (0, 0, 0, 0)
				if matrix[i][j] & 1:
					(r_path, r_val) = dp[i][j + 1]
				if matrix[i][j] & 2:
					(d_path, d_val) = dp[i + 1][j]
				total_path = r_path + d_path
				if total_path:
					dp[i][j] = [total_path if total_path < 1000000007 else total_path - 1000000007, matrix[i][j] + max(r_val, d_val)]
				else:
					dp[i][j] = [0, 0]
		return dp[0][0]


class Solution:

	def FindWays(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])
		dp = [[0] * cols for _ in range(rows)]
		for i in range(0, rows):
			for j in range(0, cols):
				if i == 0 and j == 0:
					dp[i][j] = 1
				elif i == 0:
					if matrix[i][j - 1] != 2:
						dp[i][j] = dp[i][j - 1]
				elif j == 0:
					if matrix[i - 1][j] != 1:
						dp[i][j] = dp[i - 1][j]
				else:
					if matrix[i - 1][j] != 1:
						dp[i][j] += dp[i - 1][j]
					if matrix[i][j - 1] != 2:
						dp[i][j] += dp[i][j - 1]
		path = dp[rows - 1][cols - 1] % 1000000007
		dp = [[0] * cols for _ in range(rows)]
		for i in range(0, rows):
			for j in range(0, cols):
				if i == 0 and j == 0:
					dp[i][j] = matrix[i][j]
				elif i == 0:
					if matrix[i][j - 1] != 2 and dp[i][j - 1] != 0:
						dp[i][j] = dp[i][j - 1] + matrix[i][j]
				elif j == 0:
					if matrix[i - 1][j] != 1 and dp[i - 1][j] != 0:
						dp[i][j] = dp[i - 1][j] + matrix[i][j]
				else:
					if matrix[i - 1][j] != 1 and dp[i - 1][j] != 0:
						dp[i][j] = dp[i - 1][j] + matrix[i][j]
					if matrix[i][j - 1] != 2 and dp[i][j - 1] != 0:
						dp[i][j] = max(dp[i][j - 1] + matrix[i][j], dp[i][j])
		adv = dp[rows - 1][cols - 1]
		return [path, adv]


class Solution:

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


from functools import lru_cache
import sys
from math import inf
sys.setrecursionlimit(2000)

class Solution:

	def FindWays(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dp(i, j):
			if i == n - 1 and j == m - 1:
				return 1
			if i >= n or j >= m:
				return 0
			if matrix[i][j] == 1:
				return dp(i, j + 1) % MOD
			elif matrix[i][j] == 2:
				return dp(i + 1, j) % MOD
			else:
				return (dp(i + 1, j) % MOD + dp(i, j + 1) % MOD) % MOD
		ans = []
		ans.append(dp(0, 0) % MOD)

		@lru_cache(None)
		def dp(i, j):
			if i == n - 1 and j == m - 1:
				return matrix[i][j]
			if i >= n or j >= m:
				return -inf
			if matrix[i][j] == 1:
				return matrix[i][j] + dp(i, j + 1)
			elif matrix[i][j] == 2:
				return matrix[i][j] + dp(i + 1, j)
			else:
				return matrix[i][j] + max(dp(i + 1, j), dp(i, j + 1))
		ans.append(dp(0, 0))
		return [0, 0] if ans[0] == 0 else ans


class Solution:

	def cal_max_path_sum(self, matrix, dp):
		ans = 0
		for i in range(n - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				if i == n - 1 and j == n - 1:
					continue
				if matrix[i][j] == 1:
					a = dp[i][j + 1]
					if a[1] == 0:
						dp[i][j] = [dp[i][j + 1][0], 0]
					else:
						dp[i][j] = [a[0], matrix[i][j] + a[1]]
				elif matrix[i][j] == 2:
					a = dp[i + 1][j]
					if a[1] == 0:
						dp[i][j] = [dp[i][j][0], 0]
					else:
						dp[i][j] = [a[0], matrix[i][j] + a[1]]
				else:
					a = dp[i][j + 1]
					b = dp[i + 1][j]
					if a[1] > b[1]:
						dp[i][j] = [a[0] + b[0], matrix[i][j] + a[1]]
					elif a[1] == 0 and b[1] == 0:
						dp[i][j] = [a[0] + b[0], 0]
					else:
						dp[i][j] = [a[0] + b[0], matrix[i][j] + b[1]]
		return dp[0][0]

	def FindWays(self, matrix):
		mod = 10 ** 9 + 7
		dp = []
		for i in range(n + 1):
			d = [[0, 0] for j in range(n + 1)]
			dp.append(d)
		dp[n - 1][n - 1] = [1, matrix[n - 1][n - 1]]
		ans = self.cal_max_path_sum(matrix, dp)
		if ans[0] == 0:
			return [0, 0]
		return [ans[0] % mod, ans[1] % mod]


class Solution:

	def FindWays(self, matrix):
		dp = []
		n = len(matrix)
		for i in range(n):
			dp.append([0] * n)
		dp[0][0] = [1, matrix[0][0]]
		for i in range(n):
			for j in range(n):
				if i == 0 and j == 0:
					continue
				val = 0
				maxi = 0
				if i > 0 and (matrix[i - 1][j] == 2 or matrix[i - 1][j] == 3):
					val += dp[i - 1][j][0]
					maxi = max(maxi, dp[i - 1][j][1] + matrix[i][j])
				if j > 0 and (matrix[i][j - 1] == 1 or matrix[i][j - 1] == 3):
					val += dp[i][j - 1][0]
					maxi = max(maxi, dp[i][j - 1][1] + matrix[i][j])
				dp[i][j] = [val, maxi]
				if val == 0:
					dp[i][j] = [0, 0]
		return [dp[n - 1][n - 1][0] % 1000000007, dp[n - 1][n - 1][1]]


class Solution:

	def FindWays(self, matrix):
		n = len(matrix)
		mod = 1000000007
		memory = {}

		def solve(i, j):
			if i >= n or j >= n:
				return (0, 0)
			if i == n - 1 and j == n - 1:
				return (1, matrix[i][j])
			if (i, j) in memory:
				return memory[i, j]
			right = (0, 0)
			down = (0, 0)
			if matrix[i][j] == 1:
				right = solve(i, j + 1)
			elif matrix[i][j] == 2:
				down = solve(i + 1, j)
			else:
				down = solve(i + 1, j)
				right = solve(i, j + 1)
			x = (right[0] + down[0]) % mod
			if max(right[1], down[1]) == 0:
				y = 0
			else:
				y = max(right[1], down[1]) + matrix[i][j]
			memory[i, j] = (x, y)
			return memory[i, j]
		return solve(0, 0)


class Solution:

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


class Solution:

	def FindWays(self, matrix):
		n = len(matrix)
		self.paths = 0
		dp = [[[0, -1]] * n for _ in range(n)]
		dp[-1][-1] = [1, matrix[-1][-1]]
		(path, adventure) = self.travelMaze(matrix, dp, 0, 0, n)
		return [path % int(1000000000.0 + 7), max(0, adventure) % int(1000000000.0 + 7)]

	def travelMaze(self, maze, dp, i, j, n):
		if not (0 <= i < n and 0 <= j < n):
			return [0, float('-inf')]
		if dp[i][j][1] != -1:
			return dp[i][j].copy()
		if maze[i][j] == 1:
			dp[i][j] = self.travelMaze(maze, dp, i, j + 1, n)
		elif maze[i][j] == 2:
			dp[i][j] = self.travelMaze(maze, dp, i + 1, j, n)
		else:
			right = self.travelMaze(maze, dp, i, j + 1, n)
			down = self.travelMaze(maze, dp, i + 1, j, n)
			dp[i][j] = [right[0] + down[0], max(right[1], down[1])]
		dp[i][j][1] += maze[i][j]
		return dp[i][j].copy()


class Solution:

	def FindWays(self, a):
		n = len(a)
		mod = int(1000000000.0 + 7)
		dp = [[[0, 0] for _ in range(n)] for _ in range(n)]
		dp[0][0] = [1, 0]
		for i in range(n):
			for j in range(n):
				if i and a[i - 1][j] in (2, 3):
					dp[i][j][0] += dp[i - 1][j][0]
					dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1])
				if j and a[i][j - 1] in (1, 3):
					dp[i][j][0] += dp[i][j - 1][0]
					dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][1])
				if dp[i][j][0] > 0:
					dp[i][j][0] %= mod
					dp[i][j][1] += matrix[i][j]
		return dp[n - 1][n - 1]


class Solution:

	def FindWays(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		path = [[0 for j in range(m)] for i in range(n)]
		adv = [[0 for j in range(m)] for i in range(n)]
		path[0][0] = 1
		adv[0][0] = matrix[0][0]
		for j in range(1, m):
			if path[0][j - 1] == 0:
				path[0][j] = 0
				adv[0][j] = 0
			elif path[0][j - 1] != 0 and matrix[0][j - 1] in [1, 3]:
				path[0][j] = 1
				adv[0][j] = adv[0][j - 1] + matrix[0][j]
		for i in range(1, n):
			if path[i - 1][0] == 0:
				path[i][0] = 0
				adv[i][0] = 0
			elif path[i - 1][0] != 0 and matrix[i - 1][0] in [2, 3]:
				path[i][0] = 1
				adv[i][0] = adv[i - 1][0] + matrix[i][0]
		for i in range(1, n):
			for j in range(1, m):
				(top, left) = (0, 0)
				if path[i - 1][j] != 0 and matrix[i - 1][j] in [2, 3]:
					path[i][j] += path[i - 1][j]
					top = adv[i - 1][j]
				if path[i][j - 1] != 0 and matrix[i][j - 1] in [1, 3]:
					path[i][j] += path[i][j - 1]
					left = adv[i][j - 1]
				adv[i][j] = max(top, left)
				if adv[i][j] != 0:
					adv[i][j] += matrix[i][j]
		return [path[n - 1][m - 1] % 1000000007, adv[n - 1][m - 1]]


class Solution:

	def FindWays(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		dp = [[[0, cell] for cell in col] for col in matrix]
		mod = 1000000007
		dp[0][0][0] = 1
		for i in range(n):
			for j in range(m):
				(up, down, upsum, downsum) = (0, 0, 0, 0)
				if i > 0 and (matrix[i - 1][j] == 2 or matrix[i - 1][j] == 3) and dp[i - 1][j][0]:
					up = dp[i - 1][j][0]
					upsum = dp[i - 1][j][1]
				if j > 0 and (matrix[i][j - 1] == 1 or matrix[i][j - 1] == 3) and dp[i][j - 1][0]:
					down = dp[i][j - 1][0]
					downsum = dp[i][j - 1][1]
				dp[i][j] = [max(dp[i][j][0], (up + down) % mod), dp[i][j][1] + max(upsum, downsum) % mod]
		res = [0] * 2
		res[0] = dp[n - 1][m - 1][0] % mod
		res[1] = dp[n - 1][m - 1][1] % mod if dp[n - 1][m - 1][0] != 0 else 0
		return res


mod = 1000000007

class Solution:

	def FindWays(self, matrix):
		le = len(matrix)
		dp = [[[0, 0] for i in range(le)] for j in range(le)]
		dp[0][0] = [1, 0]
		for i in range(le):
			for j in range(le):
				if i == 0 and j == 0:
					dp[i][j][1] = matrix[i][j]
				elif i == 0:
					if matrix[i][j - 1] in [1, 3] and dp[i][j - 1][0] != 0:
						dp[i][j][0] = dp[i][j - 1][0] % mod
						dp[i][j][1] = (matrix[i][j] + dp[i][j - 1][1]) % mod
				elif j == 0:
					if matrix[i - 1][j] in [2, 3] and dp[i - 1][j][0] != 0:
						dp[i][j][0] = dp[i - 1][j][0] % mod
						dp[i][j][1] = (matrix[i][j] + dp[i - 1][j][1]) % mod
				elif matrix[i][j - 1] in [1, 3] and matrix[i - 1][j] in [2, 3] and (dp[i - 1][j][0] != 0):
					dp[i][j][0] = (dp[i - 1][j][0] + dp[i][j - 1][0]) % mod
					dp[i][j][1] = (matrix[i][j] + max(dp[i - 1][j][1], dp[i][j - 1][1])) % mod
				elif matrix[i - 1][j] in [2, 3] and dp[i - 1][j][0] != 0:
					dp[i][j][0] = dp[i - 1][j][0] % mod
					dp[i][j][1] = (matrix[i][j] + dp[i - 1][j][1]) % mod
				elif matrix[i][j - 1] in [1, 3] and dp[i][j - 1][0] != 0:
					dp[i][j][0] = dp[i][j - 1][0] % mod
					dp[i][j][1] = (matrix[i][j] + dp[i][j - 1][1]) % mod
		return dp[-1][-1]


class Solution:

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


class Solution:

	def FindWays(self, matrix):
		cache = [(1, matrix[0][0])]
		for i in range(1, len(matrix[0])):
			if matrix[0][i - 1] in (1, 3) and cache[-1] is not None:
				cache.append((cache[-1][0], matrix[0][i] + cache[-1][1]))
			else:
				cache.append(None)
		for i in range(1, len(matrix)):
			if matrix[i - 1][0] in (2, 3) and cache[0] is not None:
				new_cache = [(cache[0][0], matrix[i][0] + cache[0][1])]
			else:
				new_cache = [None]
			for j in range(1, len(matrix[0])):
				from_top = cache[j] if matrix[i - 1][j] in (2, 3) else None
				from_left = new_cache[-1] if matrix[i][j - 1] in (1, 3) else None
				if from_top == from_left == None:
					new_cache.append(None)
				elif from_top is None:
					new_cache.append((from_left[0], from_left[1] + matrix[i][j]))
				elif from_left is None:
					new_cache.append((from_top[0], from_top[1] + matrix[i][j]))
				elif from_top[1] == from_left[1]:
					new_cache.append((from_left[0] + from_top[0], from_left[1] + matrix[i][j]))
				elif from_top[1] > from_left[1]:
					new_cache.append((from_left[0] + from_top[0], from_top[1] + matrix[i][j]))
				else:
					new_cache.append((from_left[0] + from_top[0], from_left[1] + matrix[i][j]))
			cache = new_cache
		if cache[-1] is None:
			return (0, 0)
		return (cache[-1][0] % (10 ** 9 + 7), cache[-1][1])


class Solution:

	def FindWays(self, matrix):
		mod = 1000000007
		n = len(matrix)
		m = len(matrix[0])
		count = [[0 for i in range(m)] for i in range(n)]
		flag = 1
		if matrix[0][0] == 1:
			flag = 0
		count[0][0] = [1, matrix[0][0]]
		for i in range(1, n):
			if flag == 1:
				count[i][0] = [1, matrix[i][0] + count[i - 1][0][1]]
			else:
				count[i][0] = [0, 0]
			if matrix[i][0] == 1:
				flag = 0
		flag = 1
		if matrix[0][0] == 2:
			flag = 0
		for i in range(1, m):
			if flag == 1:
				count[0][i] = [1, matrix[0][i] + count[0][i - 1][1]]
			else:
				count[0][i] = [0, 0]
			if matrix[0][i] == 2:
				flag = 0
		for i in range(1, n):
			for j in range(1, m):
				count[i][j] = [0, 0]
				if count[i - 1][j][0] != 0 and (matrix[i - 1][j] == 3 or matrix[i - 1][j] == 2):
					count[i][j] = [count[i][j][0] + count[i - 1][j][0], max(count[i][j][1], count[i - 1][j][1] + matrix[i][j])]
				if count[i][j - 1][0] != 0 and (matrix[i][j - 1] == 1 or matrix[i][j - 1] == 3):
					count[i][j] = [count[i][j][0] + count[i][j - 1][0], max(count[i][j][1], count[i][j - 1][1] + matrix[i][j])]
				count[i][j][0] = count[i][j][0] % mod
				count[i][j][1] = count[i][j][1] % mod
		if count[n - 1][m - 1][0] == 0:
			return (0, 0)
		return (count[n - 1][m - 1][0] % mod, count[n - 1][m - 1][1] % mod)


class Solution:

	def FindWays(self, m):
		MOD = int(1000000000.0 + 7)
		n = len(m)
		(f, g) = ([[-1e+18] * n for _ in range(n)], [[0] * n for _ in range(n)])
		f[0][0] = m[0][0]
		g[0][0] = 1
		for i in range(n):
			for j in range(n):
				if m[i][j] & 1 and j + 1 < n:
					f[i][j + 1] = max(f[i][j + 1], f[i][j] + m[i][j + 1])
					g[i][j + 1] = (g[i][j + 1] + g[i][j]) % MOD
				if m[i][j] & 2 and i + 1 < n:
					f[i + 1][j] = max(f[i + 1][j], f[i][j] + m[i + 1][j])
					g[i + 1][j] = (g[i + 1][j] + g[i][j]) % MOD
		return (g[-1][-1], max(0, f[-1][-1]))


from collections import *
from math import inf

class Solution:

	def FindWays(self, arr):
		dp = [[[0, 0] for i in range(n)] for j in range(n)]
		dp[0][0] = [1, 0]
		for i in range(n):
			for j in range(n):
				if i > 0 and arr[i - 1][j] in (2, 3):
					dp[i][j][0] += dp[i - 1][j][0]
					dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j][1])
				if j > 0 and arr[i][j - 1] in (1, 3):
					dp[i][j][0] += dp[i][j - 1][0]
					dp[i][j][1] = max(dp[i][j][1], dp[i][j - 1][1])
				if dp[i][j][0] > 0:
					dp[i][j][0] %= 10 ** 9 + 7
					dp[i][j][1] += arr[i][j]
		return [dp[-1][-1][0], dp[-1][-1][1]]


class Solution:

	def FindWays(self, matrix):
		size = len(matrix)
		result = [[[0, 0] for i in range(size)] for j in range(size)]
		result[0][0] = [1, 0]
		for i in range(size):
			for j in range(size):
				if i > 0 and matrix[i - 1][j] in (2, 3):
					result[i][j][0] += result[i - 1][j][0]
					result[i][j][1] = max(result[i][j][1], result[i - 1][j][1])
				if j > 0 and matrix[i][j - 1] in (1, 3):
					result[i][j][0] += result[i][j - 1][0]
					result[i][j][1] = max(result[i][j][1], result[i][j - 1][1])
				if result[i][j][0] > 0:
					result[i][j][0] %= 1000000007
					result[i][j][1] += matrix[i][j]
		return result[-1][-1]


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def ctPath(self, i, j, n, m, matrix, dp):
		if i >= n or j >= m:
			return 0
		if i == n - 1 and j == m - 1:
			return 1
		if dp[i][j] != -1:
			return dp[i][j]
		(right, down, right_fin, down_fin) = (0, 0, 0, 0)
		if matrix[i][j] == 1:
			right = self.ctPath(i, j + 1, n, m, matrix, dp)
		elif matrix[i][j] == 2:
			down = self.ctPath(i + 1, j, n, m, matrix, dp)
		elif matrix[i][j] == 3:
			right_fin = self.ctPath(i, j + 1, n, m, matrix, dp)
			down_fin = self.ctPath(i + 1, j, n, m, matrix, dp)
		dp[i][j] = right + down + right_fin + down_fin
		return dp[i][j]

	def maxPath(self, i, j, n, m, matrix, dp):
		if i >= n or j >= m:
			return -999999999
		if i == n - 1 and j == m - 1:
			return matrix[n - 1][m - 1]
		if dp[i][j] != -1:
			return dp[i][j]
		(right, down, right_fin, down_fin) = (-999999999, -999999999, -999999999, -999999999)
		if matrix[i][j] == 1:
			right = 1 + self.maxPath(i, j + 1, n, m, matrix, dp)
		elif matrix[i][j] == 2:
			down = 2 + self.maxPath(i + 1, j, n, m, matrix, dp)
		elif matrix[i][j] == 3:
			right_fin = 3 + self.maxPath(i, j + 1, n, m, matrix, dp)
			down_fin = 3 + self.maxPath(i + 1, j, n, m, matrix, dp)
		dp[i][j] = max(right, down, right_fin, down_fin)
		return dp[i][j]

	def FindWays(self, matrix):
		mod = 10 ** 9 + 7
		n = len(matrix)
		m = len(matrix[0])
		dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]
		maxi = self.maxPath(0, 0, n, m, matrix, dp)
		dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]
		ct = self.ctPath(0, 0, n, m, matrix, dp)
		if maxi < 0:
			maxi = 0
		return [ct % mod, maxi % mod]