You are given a m x n matrix grid. Initially, you are located at the top-left corner (0, 0), and in each step, you can only move right or down in the matrix.

Among all possible paths starting from the top-left corner (0, 0) and ending in the bottom-right corner (m - 1, n - 1), find the path with the maximum non-negative product. The product of a path is the product of all integers in the grid cells visited along the path.

Return the maximum non-negative product modulo 109 + 7. If the maximum product is negative, return -1.

Notice that the modulo is performed after getting the maximum product.

&nbsp;
Example 1:

Input: grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
Output: -1
Explanation: It is not possible to get non-negative product in the path from (0, 0) to (2, 2), so return -1.


Example 2:

Input: grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
Output: 8
Explanation: Maximum non-negative product is shown (1 * 1 * -2 * -4 * 1 = 8).


Example 3:

Input: grid = [[1,3],[0,-4]]
Output: 0
Explanation: Maximum non-negative product is shown (1 * 0 * -4 = 0).


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 15
	-4 &lt;= grid[i][j] &lt;= 4


class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        @lru_cache(None)
        def fn(i, j): 
            """Return maximum & minimum products ending at (i, j)."""
            if i == 0 and j == 0: return grid[0][0], grid[0][0]
            if i < 0 or j < 0: return -inf, inf
            if grid[i][j] == 0: return 0, 0
            mx1, mn1 = fn(i-1, j) # from top
            mx2, mn2 = fn(i, j-1) # from left 
            mx, mn = max(mx1, mx2)*grid[i][j], min(mn1, mn2)*grid[i][j]
            return (mx, mn) if grid[i][j] > 0 else (mn, mx)
        
        mx, _ = fn(m-1, n-1)
        return -1 if mx < 0 else mx % 1_000_000_007
class Solution {
    public class Pair{
        long min=Integer.MAX_VALUE,max=Integer.MIN_VALUE;
        Pair(){

        }
        Pair(long min,long max){
            this.min=min;
            this.max=max;
        }
    }
    public int maxProductPath(int[][] grid) {
        Pair[][] dp=new Pair[grid.length][grid[0].length];
        for(int r=grid.length-1;r>=0;r--){
            for(int c=grid[0].length-1;c>=0;c--){
                if(r==grid.length-1 && c==grid[0].length-1){
                    dp[r][c]=new Pair(grid[r][c],grid[r][c]);
                }else{
                    Pair hor=(c==grid[0].length-1)?new Pair():dp[r][c+1];
                    Pair ver=(r==grid.length-1)?new Pair():dp[r+1][c];
                    long min,max;
                    if(grid[r][c]>=0){
                         max=Math.max(hor.max,ver.max);
                         min=Math.min(hor.min,ver.min);
                    }else{
                         min=Math.max(hor.max,ver.max);
                         max=Math.min(hor.min,ver.min);
                    }
                        dp[r][c]=new Pair(min*grid[r][c],max*grid[r][c]);
                }
            }
        }
        int mod=(int)1e9 +7;
        return dp[0][0].max<0?-1:(int)(dp[0][0].max%mod);
    }
}
const long long MOD = 1e9 + 7;
class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        long long mx[20][20] = {0};
        long long mn[20][20] = {0};
        int row = grid.size(), col = grid[0].size();
        
        // Init
        mx[0][0] = mn[0][0] = grid[0][0];
        
        // Init the row0 and col0 to be the continuous multiply of the elements.
        for(int i = 1; i < row; i++){
            mx[i][0] = mn[i][0] = mx[i - 1][0] * grid[i][0];
        }
        for(int j = 1; j < col; j++){
            mx[0][j] = mn[0][j] = mx[0][j - 1] * grid[0][j];
        }
        
        // DP as the explanation picture shows
        for(int i = 1; i < row; i++){
            for(int j = 1; j < col; j++){
                mx[i][j] = max(max(mx[i - 1][j], mx[i][j - 1]) * grid[i][j], min(mn[i - 1][j], mn[i][j - 1]) * grid[i][j]);
                mn[i][j] = min(max(mx[i - 1][j], mx[i][j - 1]) * grid[i][j], min(mn[i - 1][j], mn[i][j - 1]) * grid[i][j]);
            }
        }
        
        return mx[row - 1][col - 1] < 0 ? -1 : mx[row - 1][col - 1] % MOD;
    }
};
var maxProductPath = function(grid) {
    const R = grid.length, C = grid[0].length;
    if (R === 0 || C === 0)
        return -1;
    
    const mat = [...Array(R)].map(() => [...Array(C)].map(() => new Array(2)));
    
    mat[0][0] = [grid[0][0], grid[0][0]];
    for (let i = 1; i < R; i++)
        mat[i][0] = [mat[i-1][0][0]*grid[i][0], mat[i-1][0][1]*grid[i][0]];
    
    for (let i = 1; i < C; i++)
        mat[0][i] = [mat[0][i-1][0]*grid[0][i], mat[0][i-1][1]*grid[0][i]];
    
    for (let i = 1; i < R; i++) {
        for (let j = 1; j < C; j++) {
            const max = Math.max(mat[i-1][j][0], mat[i][j-1][0]),
                  min = Math.min(mat[i-1][j][1], mat[i][j-1][1]);
            if (grid[i][j] >= 0)
                mat[i][j] = [max*grid[i][j], min*grid[i][j]];
            else
                mat[i][j] = [min*grid[i][j], max*grid[i][j]];
        }
    }
    
    return mat[R-1][C-1][0] >= 0 ? mat[R-1][C-1][0] % (10**9+7) : -1;
};
Maximum Non Negative Product in a Matrix