Distinct Paths in a Grid with Obstacles

You are given an M x N grid. Each cell in the grid contains either a 1 (indicating a traversable cell) or a 0 (indicating an obstacle). Your task is to determine the number of distinct paths from the top-left corner (cell (0,0)) to the bottom-right corner (cell (M-1, N-1)). You may only move either right or down at any point in time.

If a cell has a value of 0, it cannot be part of a valid path. The problem can be solved using dynamic programming. In particular, if we define dp[i][j] as the number of distinct paths to reach cell (i,j), then for a cell that is traversable (grid[i][j] = 1) the recurrence is given by:

$$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$

with the starting condition:

$$dp[0][0] = 1$$

Your solution should read input from standard input (stdin) and write its result to standard output (stdout).

inputFormat

The input begins with a line containing two space-separated integers, M and N, representing the number of rows and columns of the grid respectively. This is followed by M lines, each containing N space-separated integers (either 0 or 1) which describe the grid.

For example:

3 3
1 0 0
1 1 0
0 1 1

outputFormat

Output a single integer representing the number of distinct paths from the top-left corner to the bottom-right corner of the grid.

## sample

1 3
1 1 1

1

</p>