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