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$）で割った余りを求めてください。

入力

入力の最初の行には、2つの整数 $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つの整数として1行に出力してください。

入出力例

入力 1

3 3
1 1 1
1 100 1
1 1 1

出力 1

1808