Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS12HOPP - Hopping bunny

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.


Added by:Damir Ferizovic
Date:2012-10-20
Time limit:1s-7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 CLOJURE PERL6
Resource:High School Programming League 2012/13

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.