Counting Balanced Subsets

Problem Statement:

Farmer John's pasture can be considered as a huge two-dimensional chessboard consisting of an N×N grid of unit squares. Each cell is identified by an ordered pair ( (i,j) ) for ( 1 \leq i,j \leq N ). Some cells contain grass.

A non-empty subset of cells is called balanced if the following conditions hold:

1. Every cell in the subset contains grass.
2. The subset is 4-connected, meaning that for any two cells in the subset there exists a path between them that moves only horizontally or vertically between adjacent cells within the subset.
3. If two cells ( (x_1,y) ) and ( (x_2,y) ) with ( x_1\le x_2 ) are in the subset, then every cell ( (x,y) ) with ( x_1\le x\le x_2 ) is also in the subset.
4. If two cells ( (x,y_1) ) and ( (x,y_2) ) with ( y_1\le y_2 ) are in the subset, then every cell ( (x,y) ) with ( y_1\le y\le y_2 ) is also in the subset.

The above conditions imply that any balanced subset must form a contiguous rectangular subgrid that is completely filled with grass. Your task is to compute the number of balanced subsets (i.e. subrectangles that contain only cells with grass) modulo ( 10^9+7 ).

inputFormat

The first line contains an integer ( N ) that specifies the size of the grid.

The next ( N ) lines each contain ( N ) space-separated integers. Each integer is either 0 or 1, where 1 indicates that the cell contains grass and 0 indicates that it does not.

outputFormat

Output a single integer—the number of balanced subsets modulo ( 10^9+7 ).

sample

1
1

1