Unique Paths in a Park

You are given a rectangular grid representing a park. The park is represented as a matrix with M rows and N columns. Each cell in the grid is either empty (denoted by 0) or contains a tree (denoted by 1). Starting from the top-left corner (0, 0) and moving only right or down, your task is to find the number of unique paths to the bottom-right corner (M-1, N-1) while avoiding any cells that contain a tree.

If the starting or ending cell has a tree, there is no valid path. In an empty grid (without trees), the number of unique paths is given by the combinatorial formula:

However, due to trees blocking some paths, you need to use dynamic programming to calculate the number of unique valid paths.

inputFormat

The input will be provided via standard input (stdin) in the following format:

1. The first line contains two space-separated integers M and N representing the number of rows and columns.
2. The next M lines each contain N space-separated integers (either 0 or 1) representing the grid of the park.

outputFormat

Output the number of unique paths from the top-left corner to the bottom-right corner that avoid tree cells. The output should be written to standard output (stdout) as a single integer.

3 3
0 0 0
0 1 0
0 0 0

2