【题目背景】
经过了一次病毒的袭击,$\omega$ 国拥有了丰富的经验。
而经过大发展的 $\omega$ 国的城市布局重新改变了,变为了 $n \times n$ 的一个大网格。
而现在,出现了新的紧急状况,经过小 $\omega$ 的调查,居然每个城市内都有病毒,由于其传播能力 不强,所以没有大范围传播而被发现,第 $i$ 行第 $j$ 列的城市中含有病毒 $a_{i,j}$。
小 $\omega$ 决定彻底在 $\omega$ 国内消灭所有病毒,作为小 $\omega$ 的顶级秘书,你自然要帮助小 $\omega$ 做一些工作。
具体的,小 $\omega$ 将会先随机一个矩形(随机方式为在所有左上角是城市,右下角也是城市的矩形 中等概率随机选取一个,边长可以是 $0$,边平行于网格的边),求出里面的病毒种数,然后让医生制 造疫苗,你,要帮助小 $\omega$ 计算这个病毒的期望种数。
由于一些奇怪原因,你只要输出这个期望种数乘上 $\frac{n \times (n+1) \times n \times(n+1)}{4}$ 的值就好。
【输入格式】
从文件 viru.in
中读入数据。
第一行一个正整数 $n$ 表示网格的范围。
下面 $n$ 行,每行 $n$ 个正整数 $a_{i,j}$ 表示坐标位于 $(i,j)$ 的城市中所含有的病毒。
【输出格式】
输出到文件 viru.out
中。
一行一个数表示期望种数乘上 $\frac{n \times (n+1) \times n \times(n+1)}{4}$ 的值,由于得便的力量,它总是一个整数。
【样例 1 输入】
5
2 4 2 2 4
5 5 3 2 3
3 3 4 2 1
4 2 3 2 3
3 3 5 5 2
【样例 1 输出】
644
【样例 2 输入】
15
9 9 1 1 6 4 4 5 8 6 10 6 1 7 9
5 8 10 3 9 1 8 6 10 7 1 4 2 2 4
9 6 1 6 10 9 7 5 3 9 9 6 7 10 1
5 7 6 5 2 8 8 7 2 10 2 5 3 7 5
10 7 10 7 6 10 7 2 5 6 4 10 5 6 6
6 2 5 10 7 2 6 8 5 6 2 10 9 3 2
3 9 1 5 2 1 7 9 7 10 6 7 2 5 7
3 9 2 10 5 1 3 8 8 3 6 4 5 5 6
7 3 8 9 3 8 10 7 3 6 5 1 10 2 6
9 10 6 5 5 4 10 7 10 6 9 4 9 5 8
8 9 7 2 6 6 2 6 6 3 5 3 10 6 1
10 9 10 9 7 10 5 8 3 9 1 8 9 10 3
4 9 2 1 8 10 2 9 4 5 4 5 10 3 8
4 5 7 3 5 6 6 3 2 6 7 4 1 3 3
1 5 2 9 2 7 2 1 3 10 10 5 7 9 9
【样例 2 输出】
112292
【数据范围】
对于所有数据,保证 $1 \leq n \leq 1500$。
数据全部随机生成:随机方式为手动选取一个正整数 $W$ 满足 $1 \leq W \leq n \times n$,每个 $a_{i,j}$ 都在 $[1,W]$ 中随机生成。
【子任务】
$\text{Subtask} 1(23)$: $1 \leq n \leq 50$。 $\text{Subtask} 2(19)$: $1 \leq n \leq 100$。 $\text{Subtask} 3(17)$: $1 \leq n \leq 150$。 $\text{Subtask} 4(13)$: $1 \leq n \leq 300$。 $\text{Subtask} 5(11)$: $1 \leq n \leq 600$。 $\text{Subtask} 6(7)$: $1 \leq n \leq 800$。 $\text{Subtask} 7(5)$: $1 \leq n \leq 1000$。 $\text{Subtask} 8(3)$: $1 \leq n \leq 1300$。 $\text{Subtask} 9(2)$: 无。