Bobo 有一个 $n$ 行 $n$ 列的矩阵 $A$。

对于左上角为 $(x_1, y_1)$，右下角为 $(x_2, y_2)$ 的子矩阵（其中 $1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq n$），他定义其“偏度”为 $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 想要求出所有子矩阵的“偏度”之和，结果对 $(10^9+7)$ 取模。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$。

接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $A_{i, 1}, A_{i, 2}, \dots, A_{i, n}$。

• $1 \leq n \leq 1000$
• $0 \leq A_{i, j} \leq 10^9$
• 测试用例数量不超过 $10$。

输出格式

对于每个测试用例，输出一个整数，表示总和。

样例

样例输入 1

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

样例输出 1

14
448