网格图(grid)

Kujou Kawaii 有一张 $n$ 行 $m$ 列的网格图。行的编号为 $1 \sim n$, 列的编号为 $1 \sim m$。为了方便起见，她称位于第 $i$ 行第 $j$ 列的点为 $(i,j)$

图上每个点有点权，点 $(i,j)$ 的点权为 $a_{i,j}$。同时图上有若干条边权为 $0$ 无向边，具体的，$(i,j)$ 同 $(x,y)$ 之间有边当且仅当 $|i-x|+|j-y| = 1$。

定义一条路径的权值为经过所有点的点权之和，如果一个点出现了多次点权也需要计算多次。起点与终点也需要倍计入路径的权值之中。这里我们默认起点与终点互不相同。

假设 $(i,j)$ 至 $(x,y)$ 的最短路为 $f(i,j,x,y)$。Kujou Kawaii 非常好奇 $\sum \limits_{i=1}^n \sum \limits_{x=1}^n \sum \limits_{j=1}^m \sum \limits_{y=1}^m [(i,j) \neq (x,y)] f(i,j,x,y)$ 的值。

由于其非常之大，你只需要求出答案对 $100,000,000,7(10^9+7)$ 取模后的结果即可。

输入格式

第一行两个正整数,分别为 $n,m$。

接下来 $n$ 行，每行 $m$ 个正整数，第 $i$ 行第 $j$ 个数字表示 $a_{i,j}$。

输出格式

一行一个整数表示答案对 $10^9+7$ 取模后的结果。

样例输入1

样例输出1

数据范围

测试点 $1$: $n = 1$

测试点 $2 \sim 3$: $n \times m \le 500,a_{i,j}$ 随机生成

测试点 $4 \sim 7$: $n \times m \le 5000,a_{i,j}$ 随机生成

测试点 $8 \sim 13$: $a_{i,j}$ 随机生成

测试点 $14 \sim 17$: $m \le 5 \times 10^4$

测试点 $18 \sim 20$: 无特殊限制。

对于所有测试数据，满足 $1 \le n \le 3,1 \le m \le 1.5 \times 10^5,1 \le a_{i,j} \le 10^9$。

特殊的，对于所有编号为偶数的测试点满足 $n=3$, 对于所有编号大于 $1$ 且为奇数的测试点满足 $n=2$。

时间限制：$\texttt{3s}$

空间限制：$\texttt{512MB}$

Universal Online Judge