Rikka 是一位富有的女孩。

她想要造訪中國美麗的城市。中國的城市位置可以簡單地視為一個包含 $n$ 列與 $m$ 行的網格。列由北向南編號為 $1$ 到 $n$，行由西向東編號為 $1$ 到 $m$。位於第 $i$ 列、第 $j$ 行的城市稱為 $(i, j)$。

全國各地有一些高速公路連接。城市 $(i, j)$ 與城市 $(x, y)$ 之間有直接的高速公路，若且唯若 $|i - x| + |j - y| = 1$。由於新年即將到來，高速公路現已免費開放。

當 Rikka 從城市 $(i, j)$ 旅行到 $(x, y)$ 時，她只能透過高速公路旅行。旅行路線的成本是她所造訪的所有城市的成本總和，包含起點與終點城市。如果路線包含某個城市，她會參觀景點、購物並花錢。如果路線包含城市 $(i, j)$，她會花費 $a_{i,j}$ 元。如果她總共造訪城市 $(i, j)$ 共 $k$ 次，她將花費 $k \cdot a_{i,j}$ 元，因為總是有足夠的購物中心供她花錢。

Rikka 是一個異想天開的女孩，她甚至沒有設定起點和終點城市。她想知道所有不同起點與終點城市之間，最便宜路線的成本總和。換句話說，令 $f(i, j, x, y)$ 為從城市 $(i, j)$ 出發並以城市 $(x, y)$ 為終點的路線之最小成本。她想知道以下數值：

$$\sum_{i=1}^{n} \sum_{x=1}^{n} \sum_{j=1}^{m} \sum_{y=1}^{m} [(i, j) \neq (x, y)]f(i, j, x, y)$$

由於答案可能非常大，你只需要告訴她答案對 $1\,000\,000\,007$（即 $10^9 + 7$）取模後的結果。

輸入格式

第一行包含兩個整數 $n$ 與 $m$。 接下來的 $n$ 行，每行包含 $m$ 個整數。第 $i$ 行的第 $j$ 個數字為 $a_{i,j}$ 的值。 保證 $n = 3$，$1 \le m \le 1.5 \cdot 10^5$，且 $1 \le a_{i,j} \le 10^9$。

輸出格式

輸出單行一個整數，即答案對 $1\,000\,000\,007$（即 $10^9 + 7$）取模後的結果。

範例

輸入 1

3 3
1 1 1
1 100 1
1 1 1

輸出 1

1808