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 de numere, indexate de la 0
. Se dă o matrice A
de N
pe M
, tot indexată de la 0
, unde . 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ă:
mod ,
În alte cuvinte: se consideră sau-ul pe biți al tuturor submatricilor dreptunghiulare continue ale lui A
. Dacă aceste valori sunt unde K
este numărul de submatrici continue dreptunghiulare ale lui A, se cere mod .
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
.- .
P
are mereu lungimea
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 .
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
90
stdin
4 5
0 1 2 ... (până la 1023)
537 152 39 245 765
487 748 533 897 881
980 571 568 972 894
88 901 637 47 822
stdout
134162