You are given a N * N matrix, U. You have to choose 2 sub-matrices A and B made of only 1s of U, such that, they have at least 1 cell in common, and each matrix is not completely engulfed by the other, i.e.,

If U is of the form

and A is of the form

and B is of the form

then, there exists atleast 1 a_{i, j} : a_{i, j} ∈ A and a_{i,j} ∈ B

then, there exists atleast 1 ai1, j1 : ai1, j1 ∈ A and ai1,j1 ∉ B

then, there exists atleast 1 ai2, j2 : ai2, j2 ∈ B and ai2,j2 ∉ A

a_{x,y} = 1 ∀ a_{x,y} ∈ A

a_{x,y} = 1 ∀ a_{x,y} ∈ B

How many such (A, B) exist?

Input Format

The first line of the input contains a number N.

N lines follow, each line containing N integers (0/1) NOT separated by any space.

Output Format

Output the total number of such (A, B) pairs. If the answer is greater than or equal to 10^{9} + 7,
then print answer modulo (%) 10^{9} + 7.

Constraints

2 ≤ N ≤ 1500

a_{i,j} ∈ [0, 1] : 0 ≤ i, j ≤ N - 1

Sample Input

4
0010
0001
1010
1110

Sample Output

10

Explanation

X means the common part of A and B.

We can swap A and B to get another answer.

0010
0001
A010
XB10

0010
0001
A010
XBB0

0010
0001
10A0
1BX0

0010
0001
10A0
BBX0

0010
0001
1010
AXB0

TimeLimits

Time limit for this challenge is mentioned here

见题面

见题面