Problem description

Dany jest graf skierowany. Ile jest w nim ścieżek co najwyżej K-krawędziowych z wierzchołka 1 do wierzchołka N? Dwie ścieżki uznajemy za różne, gdy ciąg kolejnych wierzchołków pośrednich (wliczając początkowy i końcowy) różnią się.

Napisz program, który: wczyta opis grafu, wyznaczy liczbę szukanych ścieżek i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierwszu wejścia znajdują się trzy liczby całkowite N, M i K, pooddzielane pojedynczymi odstępami i określające kolejno: liczbę wierzchołków, liczbę krawędzi oraz maksymalną dozwoloną długość ścieżki.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – reszta z dzielenia przez 10⁹ + 7 liczby ścieżek z wierzchołka 1 do wierzchołka N, długości co najwyżej K krawędzi.

Ograniczenia

1 ≤ N ≤ 100, 1 ≤ M ≤ 5 000, 1 ≤ K ≤ 10⁹.

Przykład

4 7 3
1 2
1 3
2 3
1 4
2 4
3 4
4 1

5

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

3