Turism

Alex, un mare entuziast al turismului, a decis să-și transforme pasiunea într-o afacere și să organizeze tururi ale orașului Bistrița. Orașul poate fi reprezentat ca un graf orientat al obiectivelor turistice, conectate direct de străzi. Totuși, dat fiind că abilitatea de a se orienta a lui Alex nu este comparabilă cu entuziasmul lui, organizarea traseelor este dificilă pentru el. În primul rând, el vrea să numere câte astfel de trasee există în oraș. Un traseu reprezintă o listă ordonată $a$ de $k$ obiective turistice, cu următoarele proprietăți:

• De la nodul $a_i$ se poate ajunge în nodul $a_{i+1}$, pentru $1 \le i \lt k$;
• De la nodul $a_k$ se poate ajunge în nodul $a_1$.

Spunem că se poate ajunge de la nodul $x$ la nodul $y$ dacă există un drum de $0$ sau mai multe străzi care începe în nodul $x$ și se termină în nodul $y$. Există $2$ tipuri de trasee turistice:

• Tipul $1$, în care obiectivele se pot repeta;
• Tipul $2$, în care obiectivele trebuie să fie distincte.

Cerință

Graful obiectivelor turistice este un graf orientat în care o muchie de la $x$ la $y$ reprezintă un drum direct de la nodul $x$ la nodul $y$. Alex are nevoie de ajutorul vostru, pentru a determina câte trasee de lungime $k$ există pentru un tip dat de trasee turistice (Tipul $1$ sau Tipul $2$), pentru fiecare $k$ de la $1$ la $Q$.

Date de intrare

Prima linie conține $T$, tipul traseului. A doua linie conține $N$, $M$ și $Q$, reprezentând numărul de noduri și de muchii ale grafului, respectiv $k$-ul maxim pentru care Alex vrea să afle numărul de trasee. Următoarele $M$ linii conțin câte 2 numere $x$, $y$, reprezentând o muchie orientată de la $x$ la $y$.

Date de ieșire

Pentru fiecare linie $k$, de la $1$ la $Q$, se va afișa numărul de trasee de lungime $k$, modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq N \leq 300 \ 000$
• $1 \leq M,Q \leq 1 \ 000 \ 000$

Exemplul 1

turism.in

1
3 2 3
1 2
2 1

turism.out

3
5
9

Explicație

Traseele de lungime $1$ sunt: $(1)$, $(2)$, $(3)$;
Traseele de lungime $2$ sunt: $(1, 1)$, $(1, 2)$, $(2, 1)$, $(2, 2)$, $(3, 3)$;
Traseele de lungime $3$ sunt: $(1, 1, 1)$, $(1, 1, 2)$, $(1, 2, 1)$, $(2, 1, 1)$, $(1, 2, 2)$, $(2, 1, 2)$, $(2, 2, 1)$, $(2, 2, 2)$, $(3, 3, 3)$.

Exemplul 2

turism.in

2
3 2 3
1 2
2 1

turism.out

3
2
0

Explicație

Traseele de lungime $1$ sunt: $(1)$, $(2)$, $(3)$.
Traseele de lungime $2$ sunt: $(1, 2)$, $(2, 1)$.

Exemplul 3

turism.in

1
5 4 10
1 2
2 3
3 1
3 4

turism.out

5
11
29
83
245
731
2189
6563
19685
59051

Exemplul 4

turism.in

2
6 7 4
1 2
2 3
3 4
4 5
5 3
3 1
3 6

turism.out

6
20
60
120

Exemplul 5

turism.in

1
8 9 15
1 2
2 3
3 4
2 1
4 5
5 6
6 7
7 8
8 2

turism.out

8
64
512
4096
32768
262144
2097152
16777216
134217728
73741817
589934536
719476260
755810045
46480318
371842544