Problem Description
There is a directed acyclic graph with n vertices and m edges. You are allowed to delete exact k edges in such way that the lexicographically minimal topological sort of the graph is minimum possible.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains three integers n, m and k (1≤n≤100000,0≤k≤m≤200000) -- the number of vertices, the number of edges and the number of edges to delete.
For the next m lines, each line contains two integers ui and vi, which means there is a directed edge from ui to vi (1≤ui,vi≤n).
You can assume the graph is always a dag. The sum of values of n in all test cases doesn't exceed 106. The sum of values of m in all test cases doesn't exceed 2×106.
Output
For each test case, output an integer S=(∑i=1ni⋅pi) mod (109+7), where p1,p2,...,pn is the lexicographically minimal topological sort of the graph.
Sample Input
3
4 2 0
1 2
1 3
4 5 1
2 1
3 1
4 1
2 3
2 4
4 4 2
1 2
2 3
3 4
1 4
Sample Output
30
27
30
