Count Paths in an Obstacle Grid

You are given an n × m grid consisting of non-negative integers where 0 represents a free cell and 1 represents an obstacle. Your task is to find the number of distinct paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,m)), moving only down or right at each step.

Important: If the starting cell or the ending cell is blocked (i.e. contains a 1), then there is no valid path and the answer should be 0.

The transition for the dynamic programming solution can be described by the following formula:

$$\text{dp}[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = 1, \\ \text{dp}[i-1][j] + \text{dp}[i][j-1], & \text{otherwise.} \end{cases} $$

Your solution should read the input from stdin and output the result to stdout.

inputFormat

The first line of input contains two integers n and m, representing the number of rows and columns in the grid respectively. The following n lines each contain m space-separated integers (each being 0 or 1) that represent the grid.

outputFormat

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

## sample

1 1
0

1