409722: GYM103708 D Different Pass a Ports

Francovich is planning to travel the world via boat, he insists on being via boat because he really loves marine life and marine food.

In each port, he will receive a stamp in his book that keeps track of the arrival for legal purposes.

Because the book has the pages ordered the book will be different depending on the order that he visits the ports, and because he doesn't have a clear destination and want to pass by ports as many times as he can because he doesn't like direct travel. Francovich wonders what is the different numbers of ways his book of stamps can look and is your task to help him!

The ports have predefined travel routes that are bidirectional and Francovich only has enough money to do exactly $$$K$$$ travels and starts in port number 1.

The first line will have three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$2 \leq N \leq 100$$$, $$$1 \leq M \leq 5000$$$, $$$1 \leq K \leq 10^5$$$) that describe the number of ports, the number of travel routes between ports, and the number of travels that Francovich can do.

The next $$$M$$$ lines will have two integers $$$A$$$, $$$B$$$ ($$$1 \leq A,B \leq N$$$) each that describe a direct travel route between the port $$$A$$$ and the port $$$B$$$

A single integer $$$X$$$ that describes the number of ways Francovich's pass-a-port can look after his $$$K$$$ travels. Because this number can be very large print it modulo $$$10^9 + 7$$$.

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

4

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

5

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

22