A Byteland Vacation
You're planning a vacation to Byteland. It has cities, and you can travel between cities either by plane or by car. There are exactly highways in Byteland, and highway connects cities and . If you want to travel from some city to some city and there is no highway between them, you can travel the distance from to by plane.
One curious feature of Byteland is that the number of highways connecting some city to others is equal for each city in Byteland. More formally, let be the number of cities such that there is a highway directly connecting city to some city, . for all .
You want to finalize the itinerary for your Byteland vacation. You decide to visit a sequence of cities, , such that . During your trip, you'll visit each city in the sequence ; first traveling to city , then traveling from to , then traveling from to , , finally traveling from to . Be aware that you may end up visiting certain cities more than once.
Exciting Roads
There are two ways to travel from to : by plane or by car. However, your preference is to travel by car because you dislike going through airport security and waiting in endless lines.
We call a continuous subsequence, , of exciting if you can travel all the cities from to by car. More formally, is exciting if for each there is a highway between and (note that must not be equal to ).
We call the length of continuous subsequence . You want to maximize the length of maximum exciting subsequence of .
Task
You decide to take a random itinerary, (recall that , and each is a random city from to ) and follow it. You want to know the expected maximum length of a continuous exciting subsequence in your itinerary.
Input Format
The first line contains three space-seperated non-negative integers describing the respective values of (the number of cities in your itinerary), (the number of cities in Byteland), and (the number of highways in Byteland). Each line of the subsequent lines contain two space-separated positive integers describing the respective cities, and , connected by highway in Byteland.
Constraints
- ,
- There are no loops and no multiple edges in Byteland road graph.
- All roads are undirected.
- Test cases with are of the total score.
- Test cases with are of the total score
- Test cases with are of the total score
Output Format
Let the answer be an irreducible fraction, . Print the result of .
Sample Input 0
3 2 0
Sample Output 0
1
Explanation 0
There are no roads, meaning that all the exciting subsequences have length . The expected length is also .
Sample Input 1
3 3 3
1 2
2 3
3 1
Sample Output 1
333333338
Explanation 1
There are exactly different plans and there are highways connecting all the cities. There are sequences with maximum length of exciting subsequence , sequences with maximum length of exciting subseqence and sequences with maximum length of exciting subsequence .
The expected value of maximum length: .
That means, we need to print modulo . means Modulo inverse here.