You are still awful at gardening, and between you, your grass and the weeds, you are losing. Each cell in your \(n \times n\) grid-garden either contains grass (denoted as 0) or weeds (denoted as 1).

You have robotised your borrowed lawn-mower but the weeds have become so very overgrown that the lawn-mower cannot get through them. Since you are lazy however, you don't care, in fact, you kind of like the extra greenery.

You initially place the robot in the top-left corner and want it to get to the bottom right corner. The robot can move one cell to the right or one cell down (but not up or left) and the robot cannot leave the garden.

How many ways can the lawn-mower robot get to the bottom right corner of your garden, starting from the top-left corner?

Input Specification

The first line contains \(n\) \((1 \leq n \leq 2000)\) the side-length of your garden.

The next \(n\) lines contain \(n\) space-separated integers (either 0 or 1) denoting what is in that cell of the garden.

Output Specification

A single integer, the number of possible paths from the top-left to bottom-right corner.

Sample Input 1

5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 1 0 1 0
0 0 0 0 0

Sample Output 1

7

Sample Input 2

5
0 1 0 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
1 0 0 0 0

Sample Output 2

29

Sample Input 3

5
0 0 0 0 0
0 0 0 0 1
0 0 1 0 1
0 1 0 1 0
1 0 0 0 0

Sample Output 3

0

Sample Input 4

5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1

Sample Output 4

0