Graphen

Cerință

Se dă un graf cu $N$ noduri si $M$ muchii. Fiecare nod are o valoare asociata $v_i$.

Frumusețea unui graf este numărul de drumuri simple a.î valorile nodurilor să fie strict crescătoare (în ordinea parcurgerii).

Se dau $Q$ întrebări de tipul ($X, Y$), dacă ar fi existat și muchia între nodul $X$ si nodul $Y$, care ar fi fost frumusețea grafului modulo $10^9+7$?

Date de intrare

Pe prima linie se găsesc două numere întregi, $N$ și $M$.
Pe următoarea linie se vor găsi valorile $v_i$.
Pe următoarele $M$ linii se vor găsi numere de tipul $(u_i,v_i)$ cu proprietatea că există muchie între ele.
Pe următoarea linie va fi $Q$.
Pe următoarele $Q$ linii se vor găsi întrebări de tipul $X Y$.

Date de ieșire

Se vor afișa $Q$ numere, răspunsul la fiecare întrebare.

Restricții și precizări

• $1 \leq N \leq 10^5$
• $1 \leq M \leq min(\frac{N \cdot (N-1)}{2},2*10^5)$
• $1 \leq v_i \leq 10^9$
• $1 \leq Q \leq 2*10^5$
• Se garantează că întrebările nu vor conține muchii deja existente în graf

Subtaskuri

• Pentru $15p$ : $N,Q \leq10$
• Pentru alte $15p$ : $Q = 1$
• Pentru alte $70p$ : Rezolvați problema

Exemplul 1

stdin

3 2
1 2 3
1 2
1 3
1
2 3

stdout

7

Explicație

Lanțurile cu valori strict crescătoare pentru prima întrebare sunt: $(1)$, $(2)$, $(3)$, $(1,2)$, $(1,3)$, $(2,3)$, $(1,2,3)$