Nikita has a family tree consisting of members number from to . Each of the edges in the tree represents a directed relationship. Basically if there is an edge from member to , it means was born before . Now, Nikita knows that these members were born in last days and only person was born on a single day, She is interested in calculating the number of ways to assign birthdays to each of the family members.
Since the required answer can be quite large, print it modulo .
Input Format
First line of input contains a single integer denoting the number of test cases.
First line of each test case contains space separated integers denoting and respectively.
Next lines of each test case contains space separated integers and denoting a direct relationship from to .
Constraints
Scoring
- for test data.
- for test data.
- for test data.
Output Format
Output consists of only line. For each line, Print required answer modulo .
Sample Input 0
2
3 4
1 2
2 3
3 4
1 2
3 2
Sample Output 0
4
8
Explanation 0
- For test case, birthdays can be assigned as follows.
- {3, 2, 1}, member was born on day , on day , on day .
- {4, 3, 1}, member was born on day , on day , on day .
- {4, 2, 1}, member was born on day , on day , on day .
- {4, 3, 2}, member was born on day , on day , on day .