Rikka là một cô gái giàu có.
Cô ấy muốn đi thăm các thành phố xinh đẹp của Trung Quốc. Các vị trí thành phố ở Trung Quốc có thể được coi đơn giản là một lưới chứa $n$ hàng và $m$ cột. Các hàng được đánh số từ 1 đến $n$ từ bắc xuống nam, và các cột được đánh số từ 1 đến $m$ từ tây sang đông. Thành phố nằm ở hàng thứ $i$ và cột thứ $j$ được gọi là $(i, j)$.
Có một số đường cao tốc kết nối cả nước. Thành phố $(i, j)$ có đường cao tốc trực tiếp đến thành phố $(x, y)$ khi và chỉ khi $|i - x| + |j - y| = 1$. Vì năm mới sắp đến, các đường cao tốc được mở cửa cho công chúng miễn phí.
Khi Rikka đi từ thành phố $(i, j)$ đến $(x, y)$, cô ấy chỉ có thể đi qua các đường cao tốc. Chi phí của một lộ trình là tổng chi phí của tất cả các thành phố cô ấy ghé thăm, bao gồm cả thành phố bắt đầu và thành phố kết thúc. Nếu lộ trình bao gồm một thành phố nào đó, cô ấy sẽ tham quan các danh lam thắng cảnh, đi mua sắm và tiêu tiền. Nếu lộ trình bao gồm thành phố $(i, j)$, cô ấy sẽ tiêu $a_{i,j}$ nhân dân tệ. Và nếu cô ấy ghé thăm thành phố $(i, j)$ tổng cộng $k$ lần, cô ấy sẽ tiêu $k \cdot a_{i,j}$ nhân dân tệ, vì luôn có đủ các trung tâm mua sắm để cô ấy tiêu tiền.
Rikka là một cô gái mơ mộng, cô ấy thậm chí không đặt ra thành phố bắt đầu và thành phố kết thúc. Cô ấy muốn biết tổng chi phí của tất cả các lộ trình rẻ nhất với các thành phố bắt đầu và kết thúc khác nhau. Nói cách khác, gọi $f(i, j, x, y)$ là chi phí tối thiểu của lộ trình bắt đầu từ thành phố $(i, j)$ và kết thúc tại thành phố $(x, y)$. Cô ấy muốn biết giá trị:
$$\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)$$
Vì câu trả lời có thể rất lớn, bạn chỉ cần cho cô ấy biết câu trả lời theo modulo $1\,000\,000\,007$ (tức là $10^9 + 7$).
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $n$ và $m$.
Mỗi dòng trong số $n$ dòng tiếp theo chứa $m$ số nguyên. Số thứ $j$ trong dòng thứ $i$ là giá trị của $a_{i,j}$.
Đảm bảo rằng $n = 3$, $1 \le m \le 1.5 \cdot 10^5$, và $1 \le a_{i,j} \le 10^9$.
Dữ liệu ra
In ra một dòng duy nhất với một số nguyên duy nhất, là câu trả lời theo modulo $1\,000\,000\,007$ (tức là $10^9 + 7$).
Ví dụ
Dữ liệu vào 1
3 3 1 1 1 1 100 1 1 1 1
Dữ liệu ra 1
1808