== include(page="template/taskheader" task_id="matsum") ==
Poveste şi cerinţă...
Se dau două numere întregi $N, M$ şi două şiruri de numere întregi nenegative $P$, de $N$ elemente, şi $Q$, de $M$ elemente. Se defineşte apoi matricea $A$ cu $N$ linii şi $M$ coloane, unde elementul $A{~i, j~}$ de pe linia $i$ şi coloana $j$ este definit de relaţia
<tex>
A_{i, j} = (P_i \times Q_j) \texttt{ xor } P_i \texttt{ xor } Q_j
</tex>
Operatorul $xor$ reprezintă sau-ul exclusiv pe biţi, scris $^$ în C++.
Definim valoarea $S(a,b,c,d)$, pentru $1 ≤ a ≤ b ≤ N$, $1 ≤ c ≤ d ≤ M$, astfel:
<tex>
S(a,b,c,d) = \sum_{i = a}^b \sum_{j = c}^d A_{i, j}
</tex>
Akane este o fire mai curioasă, şi vrea să afle următoarea valoare:
<tex>
\sum_{1 \leq a \leq b \leq N} \sum_{1 \leq c \leq d \leq M} S(a, b, c, d)^2
</tex>
O puteţi ajuta să calculeze această valoare, modulo $10^9^ + 7$?
h2. Date de intrare
Fişierul de intrare $matsum.in$ ...
Fişierul de intrare $matsum.in$ conţine, pe primul rând, numerele $N, M$, cu semnificaţia din enunţ. Pe al doilea rând se găsesc $N$ numere, elementele şirului $P$. Pe al treilea rând se găsesc $M$ numere, elementele şirului $Q$.
h2. Date de ieşire
În fişierul de ieşire $matsum.out$ ...
În fişierul de ieşire $matsum.out$ se va afişa pe primul rând un număr întreg reprezentând valoarea cerută, modulo $10^9 + 7$.
h2. Restricţii
* $... ≤ ... ≤ ...$
h2. Exemplu
* $1 ≤ N, M ≤ 2.000$.
* $0 ≤ P{~i~}, Q{~j~} ≤ 10^4^$, pentru $1 ≤ i ≤ N, 1 ≤ j ≤ M$.
* Pentru 30 de puncte, $1 ≤ N, M ≤ 30$.
* Pentru alte 40 de puncte, $1 ≤ N, M ≤ 300$.
table(example). |_. matsum.in |_. matsum.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
| 3 1
1 1 1
0
| 20 |
| 3 1
1 2 3
0 | 84 |
| 3 2
1 2 3
1 2 | 912 |
== include(page="template/taskfooter" task_id="matsum") ==
