Simetrie

După ce a rezolvat toate problemele cu two pointers, căutare binară și ciurul lui Eratosthenes, Zăhărel și-a descoperit o nouă pasiune: matricile. Nu orice fel de matrici, ci unele… „simetrice”, după propria lui definiție.

Pentru Zăhărel, o matrice este simetrică dacă valoarea din colțul stânga-sus este egală cu valoarea din colțul dreapta-jos. Simplu, elegant și suficient cât să-i dea de lucru.

De ziua lui, colegii i-au oferit o matrice drept cadou. Ca să-l țină ocupat, i-au lansat următoarea provocare: să calculeze suma tuturor submatricilor simetrice.

Zăhărel, entuziasmat, s-a apucat imediat de treabă… dar ar aprecia puțin ajutor.

Cerință

Se citesc de la tastatură două numere naturale, $n$ și $m$, reprezentând numărul de linii, respectiv numărul de coloane ale unei matrice.

Se dă o matrice cu $n$ linii și $m$ coloane, având elemente numere naturale.

Numim submatrice orice matrice obținută prin alegerea a două linii $i_1 \le i_2$ și a două coloane $j_1 \le j_2$, care determină toate elementele aflate la intersecția liniilor și coloanelor respective.

O submatrice este considerată simetrică dacă valoarea din colțul stânga-sus este egală cu valoarea din colțul dreapta-jos, adică:

Se cere să se determine suma tuturor elementelor din toate submatricile simetrice.

Deoarece rezultatul poate fi foarte mare, se va afișa suma modulo $10^9 + 7$.

Date de intrare

Pe prima linie se găsesc două numere naturale, $n$ și $m$.

Următoarele $n$ linii conțin câte $m$ numere naturale fiecare, reprezentând elementele matricei.

Date de ieșire

Pe prima linie se va afișa un singur număr natural, reprezentând suma tuturor elementelor din toate submatricile simetrice, modulo $10^9 + 7$.

Restricții și precizări

• $1 \le n, m$
• $n \cdot m \le 200\ 000$
• Elementele matricei sunt numere naturale $\le 1\ 000\ 000\ 000$
• O submatrice poate avea dimensiunea $1 \times 1$

Subtask-uri

• Subtask 1 (20 puncte): $1 \le n, m \le 20$
• Subtask 2 (40 puncte): $1 \le n, m \le 100$
• Subtask 3 (40 puncte): $n \cdot m \le 200\ 000$

Exemplu

stdin

2 3
1 2 1
3 1 2

stdout

27

Explicație

Submatricile simetrice sunt:

• Toate submatricile $1 \times 1$ (6 bucăți);
• Submatricea determinată de liniile 1–1 și coloanele 1–3 (colțuri 1 și 1);
• Submatricea determinată de liniile 1–2 și coloanele 2–3 (colțuri 2 și 2);
• Submatricea determinată de liniile 1–2 și coloanele 1–2 (colțuri 1 și 1).

Adunând sumele tuturor acestor submatrici, obținem valoarea $27$.