There is a country named LoverLand. This place is very strange in terms of people living here and spreading love among them. So one day a monk came and decided to analyze the condition of love prevailing in this country.Here every person can love a lot many other people but he can be loved by atmost one person.

Suppose there ia a person named A, X be the set of people A loves and Z is the person who loves A. So there is no intersection among set X and Z. Monk wants to know the flow of love in the country in such a way that always person being loved comes after the lover.

Since monk is clever enough to know that no of ways of flow of love can be large so he wants to know the value modulo 10^9+7. Two direction flows are different if in one of the them, person A gets his/her position before person B , but in the other one B gets position before A.

Input Format

The first line contains a single integer T denoting the number of test cases.

The first line of each test case contains two integers, N the number of residents of Loverland, and M number of loving relationships.

The next M lines of each test case contains two integers, denoting A loves B.

Constraints

 1<=T<=10
 1<=N<=200000
 1<=M<N [1<=A,B<=N]

 The sum of M over all test cases in each input file is at most 10^6. It's guaranteed that there are no cycles.

Output Format

For each test case, print a single integer on a new line, the number of ways.