793. Count All Paths with Obstacles in Grid (Modulo 10^9+7)

Given an m x n grid where 0 means free and 1 means obstacle, count the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1,n-1), moving only RIGHT or DOWN, taken modulo 10^9 + 7. If the start or end cell is an obstacle, return 0. Implement with recursion + memoization. Input is a JSON 2D array.

Input: A JSON 2D integer array of 0s and 1s.

Output: Return an integer count mod 10^9 + 7.

Examples

Input: [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: Two paths around the central obstacle.

Input: [[0,1],[0,0]]
Output: 1
Explanation: Only path goes down then right.

Input: [[1,0],[0,0]]
Output: 0
Explanation: Start cell is blocked.

Constraints

• 1 <= m, n <= 100
• grid[i][j] in {0, 1}

Asked by