Bobo has a matrix $A$ with $n$ rows and $n$ columns.

For submatrix with upper-left corner $(x_1, y_1)$ and lower-right corner $(x_2, y_2)$ ($1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq n$), he defined its skewness $S(x_1, y_1, x_2, y_2) = \left(\sum_{i = x_1}^{x_2} \sum_{j = y_1}^{y_2} A_{i, j}\right)^3$.

Bobo would like to know the sum of skewness of all submatrices modulo $(10^9+7)$.

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains an integer $n$.

The $i$-th of following $n$ lines contains $n$ integers $A_{i, 1}, A_{i, 2}, \dots, A_{i, n}$.

• $1 \leq n \leq 1000$
• $0 \leq A_{i, j} \leq 10^9$
• The number of test cases does not exceed $10$.

Output

For each case, output an integer which denotes the sum.

Sample Input

2
0 1
1 0
3
0 1 0
1 1 0
1 0 1

Sample Output

14
448