Path Counting

Problem Description

There is an $n \times n$ grid; some cells are passable and some are obstacles.

You start at the top-left corner and may move down or right one step at a time each move. Count the number of ways to reach the bottom-right corner.

Since the answer may be large, output it modulo $10^9+7$.

Input Format

The first line contains a positive integer $n$.

The following $n$ lines each contain $n$ positive integers; $1$ means passable and $0$ means blocked.

Output Format

One integer: the answer.

Sample Input

3
1 1 1
1 0 1
1 1 1

Sample Output

2

Constraints

For $100\%$ of the data, $2\le n\le 100$, and both the top-left and bottom-right corners are passable.