题目描述

有一片狭长的城邦区域，可以看作一个 3 行 m 列的网格。第 i 行第 j 列的城市记为 (i, j)。

若两个城市在网格中曼哈顿距离为 1，则它们之间有一条双向高速路。旅行者只能沿高速路移动。

每个城市 (i, j) 有一个消费值 a_{i,j}。一条旅行路线的费用等于路线中访问过的所有城市消费值之和，包括起点和终点。如果某个城市在路线中被访问多次，那么每次访问都要重新计入费用。

现在旅行者并不指定起点和终点。对于任意两个不同城市 (i, j) 和 (x, y)，记 f(i, j, x, y) 为从 (i, j) 到 (x, y) 的最小旅行费用。

请计算所有有序不同起终点对的最小费用之和：

sum f(i, j, x, y)

其中求和范围为所有 1 <= i, x <= 3、1 <= j, y <= m 且 (i, j) != (x, y) 的城市对。

由于答案可能很大，请输出其对 1000000007 取模的结果。

输入格式

第一行包含两个整数 n, m。

接下来 n 行，每行包含 m 个整数。第 i 行第 j 个整数为 a_{i,j}。

保证 n = 3。

输出格式

输出一行一个整数，表示所有有序不同起终点对的最小旅行费用之和对 1000000007 取模后的结果。

数据范围

• n = 3
• 1 <= m <= 150000
• 1 <= a_{i,j} <= 10^9

样例

3 3
1 1 1
1 100 1
1 1 1

1808