m × n board with an integer in every cell. A token starts in the top-left corner and moves one cell right or one cell down per step until it reaches the bottom-right corner.
The product of a path is the product of the numbers in every cell the token visits, the first and the last included. Find the largest non-negative product over all paths and return it modulo 10⁹ + 7. If every path has a negative product, return -1.
Note that the maximum is taken over the true products; the modulo is applied only to the maximum once it is found.board=[[2, -1, 3], [-2, 4, -1]] → 16
The path 2 → -1 → 3 → -1 gives 6, 2 → -1 → 4 → -1 gives 8, and 2 → -2 → 4 → -1 gives 16. Nothing beats that.
board=[[3, -2], [1, 2]] → 6
There are only two paths: 3 · (-2) · 2 = -12 and 3 · 1 · 2 = 6. The answer is 6.
board=[[-1, 2], [3, 4]] → -1
Both paths start at -1 and continue through positive numbers only, so every product is negative: the answer is -1.
board[i][j] ≤ 4board=[[2, -1, 3], [-2, 4, -1]]
16
Run checks the first 3 tests in your browser. Submit checks all 65 tests on the server, hidden ones included.