== include(page="template/taskheader" task_id="droom") ==

Poveste şi cerinţă...

Excentricul Primar Droom a implementat un nou sistem de drumuri ciudat in municipiul Suieb. Municipiul poate fi reprezentat drept un graf neorientat cu $N$ noduri si $M$ muchii. Se retine ca pot exista si muchii paralele. Intai numeroteaza zilele consecutiv, incepand cu ziua $0$. In ziua $0$, impune un sens unic tuturor drumurilor, acest sens fiind dat. De asemenea, defineste $f(i)$ ca fiind suma, modulo $2$, a cifrelor lui $i$, cand $i$ este scris in baza $2$. In ziua $i$, daca $f(i) = 0$, atunci drumurile sunt cu sens unic in aceeasi directie ca in ziua $0$, pe cand, daca $f(i) = 1$, atunci drumurile sunt cu sens unic in directie opusa. De asemenea, acesta mai introduce o noua regula: trebuie sa treci exact o data pe zi de la o intersectie la alta – desigur, folosind drumurile in directia specifica zilei date. Se garanteaza ca acest lucru este posibil in orice intersectie, in orice zi. Gabitza, un cetatean inocent al municipiului, isi pune intrebarea: dandu-se $Q$ tupluri $(a[~i~], b[~i~], c[~i~])$, si presupunand ca Gabitza este la intersectia a[~i~] in ziua $0$, in cate moduri poate Gabi sa ajunga la intersectia b[~i~] in ziua c[~i~], modulo $10^9^+7$?

h2. Date de intrare

Fişierul de intrare $droom.in$ ...

Fişierul de intrare $droom.in$ va contine pe prima linie un numar $T$, numarul de teste.
Fiecare test este format din mai multe randuri. Primul rand contine doua numere naturale $N$, $M$. Urmatoarele $M$ randuri contin perechi de numere $x, y$, reprezentand ca exista un drum intre intersectiile $x$ si $y$, drumul avand sens unic de la $x$ spre $y$ in ziua $0$. Urmatorul rand contine $Q$. Urmatoarele $Q$ randuri contin valorile $(a[~i~], b[~i~], c[~i~])$, in ordine.
 

h2. Date de ieşire

În fişierul de ieşire $droom.out$ ...

În fişierul de ieşire $droom.out$ va contine raspunsurile pentru fiecare test, in ordine.
Pentru fiecare test, se va afisa, pe cate un rand, raspunsul pentru fiecare tuplu $(a[~i~], b[~i~], c[~i~])$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 20$
* $M ≤ 10.000$
* $Q ≤ 200$
* $1 ≤ a[~i~],b[~i~] ≤ N$
* $0 ≤ c[~i~] ≤ 10^18^$
* $T ≤ 50$

h2. Exemplu
table(example). |_. droom.in |_. droom.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
3 7
3 2
3 2
2 1
1 3
3 2
1 3
2 1
3
1 3 7
1 3 6
1 3 6
3 8
1 2
1 2
1 3
2 3
3 2
2 1
3 1
3 1
3
3 2 8
3 2 4
2 1 2
| 1
0
0
85
5
1

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="droom") ==