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

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 numara zilele consecutiv, incepand cu ziua $0$. In ziua $0$, impune un sens unic tuturor drumurilor, acest sens fiind. De asemenea, defineste $f(i)$ ca fiind suma, modulo $2$, a cifrelor lui $i$, cand $i$ este scris in baza $2$. Intr-o zi $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$?

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$ va contine pe prima linie un numar $T$, numarul de teste.

Fiecare test este format din cateva randuri. Primul rand contine doua numere naturale $N$, $M$. Urmatoarele M randuri contin perechi de numere $a$ $b$, reprezentand ca exista un drum intre intersectiile $a$ $b$ si ca drumul este cu sens unic de la $a$ spre $b$, in ziua $0$. Urmatorul rand contine $Q$. Urmatoarele Q randuri contin valorile a[~i~], b[~i~], c[~i~], in ordine.

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$ va contine raspunsurile pentru fiecare test, in ordine. La fiecare test, se va afisa raspunsul pentru fiecare cerinta in ordine, pe randuri separate.

Î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