Labyrinthian Possibilities

You are given an N by M matrix of 0s and 1s. Starting from the top left corner, how many ways are there to reach the bottom right corner? Mod the result by 10 ** 9 + 7.

You can only move right and down. 0 represents an empty space while 1 represents a wall you cannot walk through. The top left corner and bottom right corner will always be 0.

Constraints

• 1 ≤ n, m ≤ 250 where n and m are the number of rows and columns in matrix.

https://binarysearch.com/problems/Labyrinthian-Possibilities

Examples

Example 1

Input

• matrix =

[[0,0,1],
 [0,0,1],
 [1,0,0]]

Output

• answer = 2

Explanation

There are two ways to get to the bottom right:

• Right, down, down, right
• Down, right, down, right

Example 2

Input

• matrix =

[[0,0,0],
 [0,0,0],
 [0,0,0]]

Output

• answer = 6

Explanation

There are 6 ways here:

• Right, right, down, down
• Down, down, right, right
• Right, down, right, down
• Down, right, down, right
• Right, down, down, right
• Down, right, right, down

Example 3

Input

• matrix =

[[0,0,0],
 [1,1,1],
 [0,0,0]]

Output

• answer = 0

Explanation

There is a wall in the middle preventing us from getting to the bottom right.

Example 4

Input

• matrix =

[[0,0,0,0],
 [1,1,1,0],
 [0,0,0,0]]

Output

• answer = 1

Example 5

Input

• matrix =

[[0,0,0,0,0],
 [1,1,1,0,0],
 [0,0,0,0,0]]

Output

• answer = 3

Solution