403224: GYM101081 G 7168 – SMOK

The dragon of Wawel's hill dwelt a cavern in this hill located in Krakow, Poland. Stories about the existence of this dragon dates back to the 12th century. In 1970 a bronze sculpture was constructed in the place where the dragon may have lived. This sculpture breathes fire from time to time, or when someone sends an SMS with the word "SMOK" (dragon in polish) to the number 7168.

According to legend, King Krak, the founder, promised his daughter's hand in marriage to the who kills the dragon. Several of the bravest knights attempted this without success, and many were killed by the beast. In the search for a brave warrior to solve the problem, the King Krak sent messengers to various polish cities.

The King Krak was a religious person, and believed in the mysticism of the numbers. He wanted his messengers to spread the news to all the villages, but the messengers had to go through exactly K roads between the start and final cites, and no two messengers could take exactly the same path. He did not forbid the messengers to pass through a village or road several times.

After many years of unsuccessful trials, the King Krak himself decided that he would kill the dragon, but was stopped by Skuba, an apprentice shoemaker, that told him that he found a way to kill the beast. Skuba took a fat sheep, killed it and filled with tar and sulfur. This sheep was left during the night (while the dragon was sleeping) in the entrance of the cavern. The next day, in the morning, the city was awakened by a violent explosion: the dragon swallowed the sheep, and had a terrible thirst. After drinking a lot of water from the river, his belly exploded, and pieces of the dragon covered all the city. As promised, the hand of the princess is offered to Skuba, they got married a lived happy forever.

Your task in this problem is, given an integer K, determine how many messengers could be sent from a starting city to the corresponding final city such that all messengers pass walk through exactly K roads, and no two messengers use the exact same path.

The first line has three integers N, M and K, N is the number of cities in the kingdom, M is the number of roads, and K is the number of roads the messengers must go through. Cities are numbered from 1 to N.

The following M lines each describe a road with two distinct integers A_i and B_i, meaning there is a bidirectional road between cities A_i and B_i. There may be more than one road between two cities.

Limits

• 2 ≤ N ≤ 10²
• 1 ≤ M ≤ 2·10⁴
• 1 ≤ K ≤ 10³
• 1 ≤ A_i, B_i ≤ N

Print N - 1 lines, the ith line should contain N - i integers, the jth integer on the ith line should be the number of messengers when the starting city is i and the final city is i + j. If it is not possible to send any messenger, print  - 1, otherwise print the result modulo 10⁹ + 7.

3 2 3
1 2
2 3

2 -1 
2 

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

553 1323 183 183 
477 42 42 
427 427 
60