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 \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$.
Output
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.
