Counting Topological Sorts

In this problem, you are given a Directed Acyclic Graph (DAG) with (n) nodes and (m) edges. Your task is to count the number of valid topological orderings of the nodes modulo (10^9+7). A topological ordering is an arrangement of the nodes such that for every edge (u \to v), node (u) appears before node (v). This problem may require a brute force approach since (n) is small. Use the input format specified to read from standard input and output the result to standard output.

inputFormat

The first line contains an integer (T) representing the number of test cases. For each test case, the first line contains two integers (n) and (m) denoting the number of nodes and edges, respectively. The next (m) lines each contain two integers (u) and (v) representing a directed edge from node (u) to node (v). Nodes are numbered from 1 to (n).

outputFormat

For each test case, output a single line that contains the number of valid topological orderings modulo (10^9+7).## sample

1
3 2
1 2
1 3

2