Rezolvare PBinfo #4566

Cerința

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} \)
• 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

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 ≤ N ≤ 300 000
• 1 ≤ M, Q ≤ 1 000 000

Punctare

• Pentru 7 puncte, T = 1, 1 ≤ N ≤ 6, 1 ≤ M ≤ 30, 1 ≤ Q ≤ 30.
• Pentru alte 15 puncte, T = 1, 1 ≤ N, Q ≤ 50, 1 ≤ M ≤ 100.
• Pentru alte 17 puncte, T = 1, 1 ≤ N, Q ≤ 1000, 1 ≤ M ≤ 2000.
• Pentru alte 21 de puncte, T = 1, 1 ≤ N, Q ≤ 100 000, 1 ≤ M ≤ 200 000.
• Pentru alte 8 puncte, T = 2, 1 ≤ N, Q ≤ 1000, 1 ≤ M ≤ 2000.
• Pentru alte 20 de puncte, T = 2, 1 ≤ N, Q ≤ 100 000, 1 ≤ M ≤ 200 000.
• Pentru restul de 12 puncte, T = 2, 1 ≤ N ≤ 300 000, 1 ≤ M, Q ≤ 1 000 000.

Exemplu 1:

turism.in

1
3 2 3
1 2
2 1

turism.out

3
5
9

Exemplu 2:

turism.in

2
3 2 3
1 2
2 1

turism.out

3
2
0

Exemplu 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

Exemplu 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

Exemplu 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

Explicații

Pentru primul exemplu, traseele sunt:

• (1), (2), (3) – lungime 1
• (1, 1), (1, 2), (2, 1), (2, 2), (3, 3) – lungime 2
• (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) – lungime 3

Pentru al doilea exemplu, traseele sunt:

• (1), (2), (3) – lungime 1
• (1, 2), (2, 1) – lungime 2