2013年7月12日 星期五

11174 - Stand in a Line


Problem J
Stand in a Line
Input: Standard Input
Output: Standard Output

在 byteland 中,所有的人們都要站成一直線,而沒有人站在他父親的前面。給定在 byteland 人們的父子關係 ,問有多少組排列方法使得他們排成一直線。
Input
測資第一有一個整數 T ( T < 14) 表示測資組數。

每組測資會有兩個整數 n, m (1≤n≤40000, 0≤m<n),n 表示現在有多少人們,m 表示有多少人的父親還活著,而人們的編號為 1 到 n,接下來會有 m 行,每行上有兩個整數 a, b,表示 b 是 a 的父親。一個人最多只會有一位父親,且沒有人的祖先會他自己。

Output

對於每組測資,輸出一行答案 mod  1000000007 後的結果。

Sample Input                                  Output for Sample Input

3
3 2
2 1
3 1
3 0
3 1
2 1
 
2
6
3



Problem setter: Abdullah-al-Mahmud
Special Thanks: Derek Kisman