Matsum

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

$\displaystyle A_{i,j} = (P_i \cdot Q_j) \text{ xor } P_i \text{ xor } Q_j$

Operatorul xor reprezintă sau-ul exclusiv pe biți, scris ^ în C++.

Definim valoarea $S(a, b, c, d)$, pentru $1 \le a \le b \le N$, $1 \le c \le d \le M$, astfel:

$\displaystyle S(a, b, c, d) = \sum_{i=a}^{b} \sum_{j=c}^{d} A_{i,j}$

Akane este o fire mai curioasă, și vrea să afle următoarea valoare:

$\displaystyle \sum_{1 \le a \le b \le N} \sum_{1 \le c \le d \le M} {S(a, b, c, d)}^2$

O puteți ajuta să calculeze această valoare, modulo $10^9 + 7$?

Date de intrare

Pe primul rând se găsesc 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$.

Date de ieșire

Se va afișa pe primul rând un număr întreg reprezentând valoarea cerută, modulo $10^9 + 7$.

Restricții

• $1 \le N, M \le 2 \ 000$.
• $0 \le P_i, Q_j \le 10^4$, pentru $1 \le i \le N; 1 \le j \le M$.

Subtask 1 (30 puncte)

• $1 \le N, M \le 30$.

Subtask 2 (40 puncte)

• $1 \le N, M \le 300$.

Subtask 3 (30 puncte)

• Fără restricții suplimentare

Exemple

stdin

3 1
1 1 1
0

stdout

20

stdin

3 1
1 2 3
0

stdout

84

stdin

3 2
1 2 3
1 2

stdout

912

Explicații

Pentru primul exemplu avem ca $A = \begin{bmatrix} 1 \\ 1 \\ 1 \\ \end{bmatrix}$.
Vor fi $3$ submatrici formate dintr-un singur element care vor avea valoarea $S$ egală cu $1$, $2$ submatrici formate din $2$ elemente care vor avea valoarea $S$ egală cu $2^2 = 4$ și în cele din urma, matricea întreagă care va avea valoarea 32 = 9. Însumând aceste valori obținem $1 \cdot 3 + 2 \cdot 4 + 1 \cdot 9 = 20$. $20 \text{ modulo } 10^9 + 7$ este chiar $20$.
Pentru ultimul exemplu, $A = \begin{bmatrix} 1 & 1 \\ 1 & 4 \\ 1 & 7 \\ \end{bmatrix}$.