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.

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 \le n \le 100000, 0 \le k \le m \le 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 $u_i$ and $v_i$, which means there is a directed edge from $u_i$ to $v_i$ $(1 \le u_i, v_i \le n)$.

You can assume the graph is always a dag. The sum of values of $n$ in all test cases doesn't exceed $10^6$. The sum of values of $m$ in all test cases doesn't exceed $2 \times 10^6$.

For each test case, output an integer $S = (\displaystyle\sum_{i=1}^{n}{i\cdot p_i}) \text{ mod } (10^9 + 7)$, where $p_{1}, p_{2}, ..., p_{n}$ is the lexicographically minimal topological sort of the graph.

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

30
27
30

BestCoder Round #74 (div.2)