Unique Paths with Obstacles

You are given a grid of size \( n \times m \) where each cell is either free (represented by 0) or an obstacle (represented by 1). Your task is to calculate the number of unique paths from the top-left corner of the grid (cell \((0,0)\)) to the bottom-right corner (cell \((n-1, m-1)\)), moving only down or right at any point in time.

If the starting or destination cell is an obstacle, then the answer should be 0. The grid is represented in the input such that the first line contains two integers \(n\) and \(m\) indicating the number of rows and columns, followed by \(n\) lines each containing \(m\) space separated integers (either 0 or 1). The problem must be solved using dynamic programming.

Note: Input is taken from standard input (stdin) and output is printed to standard output (stdout).

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of rows and columns respectively). Each of the following \(n\) lines contains \(m\) space-separated integers representing the grid where 0 denotes an open cell and 1 denotes an obstacle.

For example:

3 3
0 0 0
0 1 0
0 0 0

outputFormat

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

For the input example above, the output should be:

2

## sample

3 3
0 0 0
0 1 0
0 0 0

2