Рикка — богатая девушка.

Она хочет посетить прекрасные города Китая. Расположение городов в Китае можно представить в виде сетки, содержащей $n$ строк и $m$ столбцов. Строки пронумерованы от $1$ до $n$ с севера на юг, а столбцы — от $1$ до $m$ с запада на восток. Город, расположенный в $i$-й строке и $j$-м столбце, называется $(i, j)$.

В стране есть сеть скоростных автомагистралей. Город $(i, j)$ имеет прямую автомагистраль до города $(x, y)$ тогда и только тогда, когда $|i - x| + |j - y| = 1$. В связи с приближением Нового года проезд по автомагистралям стал бесплатным.

Когда Рикка путешествует из города $(i, j)$ в город $(x, y)$, она может передвигаться только по автомагистралям. Стоимость маршрута — это сумма стоимостей всех посещенных городов, включая начальный и конечный. Если маршрут включает какой-то город, она посещает достопримечательности, ходит по магазинам и тратит деньги. Если маршрут включает город $(i, j)$, она потратит $a_{i,j}$ юаней. Если она посетит город $(i, j)$ в общей сложности $k$ раз, она потратит $k \cdot a_{i,j}$ юаней, так как торговых центров всегда достаточно.

Рикка — причудливая девушка, она даже не выбирает начальный и конечный города. Она хочет узнать сумму стоимостей всех кратчайших маршрутов для всех пар различных начальных и конечных городов. Иными словами, пусть $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$ целых чисел. $j$-е число в $i$-й строке — это значение $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