Unique Paths in a Grid

You are given an (M \times M) grid, where each cell is either open (denoted by 0) or blocked (denoted by 1). Your task is to compute the number of distinct paths from the top-left corner to the bottom-right corner. You may only move either down or right at each step, and you cannot enter a blocked cell.

It can be solved using dynamic programming. If we let (dp[i][j]) be the number of ways to reach cell ((i,j)), then for an open cell, the recurrence is given by (dp[i][j] = dp[i-1][j] + dp[i][j-1]). If either the starting cell or the destination cell is blocked, the answer is 0.

inputFormat

The input is read from standard input (stdin).

The first line contains an integer (M), representing the size of the grid. Each of the following (M) lines contains a string of exactly (M) characters. Each character is either '0' (representing an open cell) or '1' (representing a blocked cell).

outputFormat

Output a single integer to standard output (stdout) — the number of distinct paths from the top-left corner to the bottom-right corner following the movement restrictions.## sample

3
000
010
000

2