Unique Paths With Obstacles

grid has 0 (free) and 1 (blocked). A robot moves right or down from the top-left to the bottom-right cell, only through free cells. Return the number of paths. Return the answer modulo 10**9 + 7.

For [[0, 0, 0], [0, 1, 0], [0, 0, 0]] the answer is 2.

Examples

Example 1

Input:

unique_paths_obstacles([[0, 0, 0], [0, 1, 0], [0, 0, 0]])

Output:

2

Example 2

Input:

unique_paths_obstacles([[0, 1], [0, 0]])

Output:

1

Constraints

• 0 <= rows, cols <= 500
• Every cell is 0 or 1.