Problem 97: Saumat

Precum în toate zilele, Toronaga-san a hotărât ca și astăzi să îl sâcâie pe Paisen. În acest scop, după ce s-au terminat orele, ea scoate din rucsac random o problema de informatică cu care îl confruntă pe Paisen. Ca deobicei Paisen nu prea face față la sâcâială, și nu prea știe să facă problema, dar poate voi îl puteți ajuta.

Se dă un șir P de $2^{10}$ de numere, indexate de la 0. Se dă o matrice A de N pe M, tot indexată de la 0, unde $0 ≤ A[i][j] < 2^{10}$ . Definim S(i, j, k, l) ca fiind sau-ul pe biți al submatricii dreptunghiulare continue a lui A ce începe pe rândul i și coloana k și se termină pe rândul j și coloana l. Se cere următoarea sumă:
$\displaystyle v(S) = \left(\sum_{0 ≤ i ≤ j < N } \sum_{0 ≤ k ≤ l < M } P[S(i,j,k,l)]\right)$ mod $10^9 + 7$ ,

În alte cuvinte: se consideră sau-ul pe biți al tuturor submatricilor dreptunghiulare continue ale lui A. Dacă aceste valori sunt $v_1, ... , v_K$ unde K este numărul de submatrici continue dreptunghiulare ale lui A, se cere $P[v_1] + . . . + P[v_K]$ mod $10^9 + 7$ .

Date de intrare

Pe prima linie se găsesc 2 numere întregi N M ce reprezintă numărul de linii, respectiv de coloane al matricei A. Pe următoarea linie se vor găsi elementele șirului P separate prin spații. Pe următoarele N linii se vor găsi câte M elemente separate prin spații, elementele matricii A.

Date de ieșire

Se va afișa pe o singură linie rezultatul cerut, v(S).

Restricții și precizări

N · M ≤ 2 000 000.
$0 ≤ P[i] ≤ 10^9$ .
P are mereu lungimea $2^{10}$

Subtask 1 (3 puncte)

N, M ≤ 20

Subtask 2 (4 puncte)

N, M ≤ 100

Subtask 3 (9 puncte)

N = 1

Subtask 4 (9 puncte)

Fiecare A[i][j] este ales uniform și independent din ${0, . . . , 2^{10} − 1}$ .

Subtask 5 (17 puncte)

P[i] = i

Subtask 6 (11 puncte)

N, M ≤ 600

Subtask 7 (47 puncte)

Fără restricții suplimentare.

Exemple

stdin

3 3
0 1 2 ... (până la 1023)
1 2 3
1 2 3
1 2 3

stdout