Problem 3352: Parada

Cerință

La parada organizată cu ocazia zilei naționale, elevii liceelor mitilare din orașele $A$ și $B$ au fost mai întâi aranjați în coloană în ordinea crescătoare a înălțimilor (o coloană cu elevii din orașul $A$ și una cu elevii din orașul $B$ ).
Ulterior ei urmează să fie rearanjați astfel încât să formeze toți o singură coloană care să îndeplinească următoarele condiții:

Elevii să fie aranjați în ordine crescătoare;
Oricare doi elevi să își păstreze ordinea relativă de la aranjarea inițială (dacă elevii $x$ și $y$ erau în același oraș și $x$ era așezat înaintea lui $y$ , în coloana reunită trebuie, de asemenea ca $x$ să fie înaintea lui $y$ , evident, nu neapărat imediat înainte);

Se cere să calculăm numărul de variante de rearanjare. Două variante diferă dacă există cel puțin o poziție pe care în prima variantă era uașezat $n$ elev și în a doua variantă era așezat alte elev.

Date de intrare

Pe prima linie a fișierului parada.in se află un număr $n$ reprezentând numărul de elevi din orașul $A$ . Pe linia a doua se află $n$ numere naturale nenule, separate prin spațiu, în ordine crescătoare, reprezentând înălțimile elevilor din orașul $A$ . Pe linia a treia se află un număr $m$ reprezentând numărul de elevi din orașul $B$ . Pe linia a patra se află $m$ numere naturale nenule, separate prin spații, în ordine crescătoare reprezentând înălțimile elevilor din orașul $B$ .

Date de ieșire

Fișierul parada.out va conține restul împărțirii valorii cerute la numărul $1 \ 000 \ 000 \ 007$ .

Restricții și precizări

$1 \leq n, m \leq 2 \ 000$ ;
Înălțimile elevilor sunt numere naturale nenule de maxim $9$ cifre.
Pentru teste în valoare de $66$ puncte înalțimile sunt numere naturale nenule de maxim $6$ cifre;
Pentru teste in valoare de $34$ puncte numerele care reprezintă înălțimile elevilor au cel puțin $8$ cifre;
Pentru teste in valoare de $33$ puncte elevii din același oraș au înălțimi distincte.

Exemplul 1

parada.in

parada.out

Explicație

1(A1) 3(A2) 3(A3) 3(A4) 3(B1) 3(B2) 4(A5) 5(B3)
1(A1) 3(A2) 3(A3) 3(B1) 3(A4) 3(B2) 4(A5) 5(B3)
1(A1) 3(A2) 3(B1) 3(A3) 3(A4) 3(B2) 4(A5) 5(B3)
1(A1) 3(B1) 3(A2) 3(A3) 3(A4) 3(B2) 4(A5) 5(B3)
1(A1) 3(A2) 3(A3) 3(B1) 3(B2) 3(A4) 4(A5) 5(B3)
1(A1) 3(A2) 3(B1) 3(A3) 3(B2) 3(A4) 4(A5) 5(B3)
1(A1) 3(B1) 3(A2) 3(A3) 3(B2) 3(A4) 4(A5) 5(B3)
1(A1) 3(A2) 3(B1) 3(B2) 3(A3) 3(A4) 4(A5) 5(B3)
1(A1) 3(B1) 3(A2) 3(B2) 3(A3) 3(A4) 4(A5) 5(B3)
1(A1) 3(B1) 3(B2) 3(A2) 3(A3) 3(A4) 4(A5) 5(B3)

Parada