High School Programming League Problems Archive

Today, as you were walking home, you saw a bunny several meters away from you. It seemed as though the bunny was confused and couldn't decide which way to go next. Watching the bunny, you thought about calculating the number of ways the bunny could reach some locations after exactly K hops. Since you couldn't find a way to do this on the spot, you decided to take down on a piece of paper the possible hops the bunny could do through the field, and to continue on your way home. Now you have to calculate the number of ways the bunny can reach all of the N locations you took note of. As this number can be very big, you want to calculate the solution modulo 1000000007.

Input

The first line contains 3 integers N, M, K (1 ≤ N ≤ 40, 1 ≤ M ≤ 100,000, 1 ≤ K ≤ 10^1000) - the number of locations which have to be considered, the number of different types of allowed hops, and the number of hops the bunny is supposed to perform, respectively. The next M lines contain 2 integers a, b each (1 ≤ a, b ≤ N), with each pair representing a possible hop from a to b. Several hops can appear more than once - consider them as different. The bunny is initially positioned at the location with number 1. There are 10 input sets.

Output

Output N lines, where the i-th (0-indexed) line contains the number of ways the bunny can reach the (i+1)-th location.

Example

Input:
4 6 2
1 2
2 1
1 1
1 2
2 4
1 3

Output:
3
2
1
2


Explanation:
All possible paths with 2 hops are: (1,1,1), (1,2,1), (1,2,1), (1,1,2), (1,1,2), (1,1,3), (1,2,4), (1,2,4).
Note: paths with the same sequence of locations exist, since different hops can be taken with the same start and end.

Scoring

By solving this problem you score 10 points.