G. 富有挑战的图上问题
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

自从上次之后，Kendieer 领略了更多关于哈密顿路径的知识，现在他决定向你提出一个挑战：

给定一个由 $$$n$$$ 个顶点组成的有向无环图 $$$G$$$，求对于该图 $$$G$$$，共有多少条不同的哈密顿路径$$$^\ast$$$，这个结果可能很大，你需要将结果对 $$$10^9 + 7$$$ 取模后输出。

$$$\ast$$$ 哈密顿路径：对于一个图上的路径，如果该路径满足过图上所有点有且仅有一次，则称这个路径为哈密顿路径。

将图中的每条边视为唯一的对象（例如按照输入顺序编号为 $$$1, 2, \dots, m$$$）。两条路径不同，当且仅当它们使用的边的编号序列不同。

Input

第一行输入一个正整数 $$$T(1\le T\le 10^4)$$$，表示测试数据组数。

接下来的 $$$T$$$ 组数据，每组输入格式如下：

  • 第一行输入两个正整数 $$$n,m(2\le n\le 2\times 10^5,n-1\le m\le 4\times 10^5)$$$，表示该图顶点个数和边的个数。
  • 接下来的 $$$m$$$ 行，每行输入 $$$2$$$ 个正整数 $$$u,v(1\le u,v\le n,u\neq v)$$$，表示一条 $$$u$$$ 指向 $$$v$$$ 的有向边。

此外，数据保证所有测试点 $$$n$$$ 的总和不超过 $$$2\times 10^5$$$，$$$m$$$ 的总和不超过 $$$4\times 10^5$$$，且保证给出的图一定是有向无环连通图。

Output

对于每组数据，输出一个非负整数，表示结果对 $$$10^9 + 7$$$ 取模后的答案。

Example
Input
3
4 4
2 1
2 3
1 4
3 4
2 3
1 2
1 2
1 2
5 7
1 2
1 3
2 3
2 5
3 4
3 5
4 5
Output
0
3
1
Note

对于第一组样例，其图如下：

对于第三组样例，其图如下：

该图仅存在一条哈密顿路径：$$$1\to 2\to 3\to 4\to 5$$$。