== 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$ (1 <= N <= 20 ) noduri si $M$ (M<=10.000) muchii. Se retine ca pot exista si muchii paralele. Intai numara zilele consecutiv, incepand cu ziua $0$. In ziua $0$, el face toate drumurile cu sens unic, intr-o directie data. De asemenea, defineste f(i) drept suma modulo 2 a cifrelor lui $i$. 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: poti trece doar o data pe zi de la o intersectie la alta – desigur, folosind drumurile regulamentare, adica 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$( Q <= 200 ), trei valori $a$, $b$, $c$, ($) 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 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$?

h2. Date de intrare