#P1662C. European Trip
European Trip
Description
The map of Europe can be represented by a set of cities, numbered from through , which are connected by bidirectional roads, each of which connects two distinct cities. A trip of length is a sequence of cities such that there is a road connecting each consecutive pair , of cities, for all . A special trip is a trip that does not use the same road twice in a row, i.e., a sequence of cities such that it forms a trip and , for all .
Given an integer , compute the number of distinct special trips of length which begin and end in the same city. Since the answer might be large, give the answer modulo .
The first line contains three integers , and (, , ) — the number of cities, the number of roads and the length of trips to consider.
Each of the following lines contains a pair of distinct integers and () — each pair represents a road connecting cities and . It is guaranteed that the roads are distinct (i.e., each pair of cities is connected by at most one road).
Print the number of special trips of length which begin and end in the same city, modulo .
Input
The first line contains three integers , and (, , ) — the number of cities, the number of roads and the length of trips to consider.
Each of the following lines contains a pair of distinct integers and () — each pair represents a road connecting cities and . It is guaranteed that the roads are distinct (i.e., each pair of cities is connected by at most one road).
Output
Print the number of special trips of length which begin and end in the same city, modulo .
Note
In the first sample, we are looking for special trips of length , but since we cannot use the same road twice once we step away from a city we cannot go back, so the answer is .
In the second sample, we have the following special trips of length which begin and end in the same city: , , , , , , , , , , , and .