Now you have a stack and $n$ numbers $1,2,3,…,n$. These $n$ numbers are pushed in the order and popped if the number is at the top of the stack. You can read the sample to get more details.
This question is quite easy. Therefore I must give you some limits.
There are $m$ limits, each is expressed as a pair$<A,B>$ means the number $A$ must be popped before $B$.
Could you tell me the number of ways that are legal in these limits?
I know the answer may be so large, so you can just tell me the answer mod $1000000007({10}^{9}+7)$.

The first line contains an integer $T$(about 5),indicating the number of cases.
Each test case begins with two integers $n(1 \leq n \leq 300)$ and $m(1 \leq m \leq 90000)$.
Next $m$ lines contains two integers $A$ and $B(1 \leq A \leq n,1 \leq B \leq n)$
(P.S. there may be the same limits or contradict limits.)

For each case, output an integer means the answer mod $1000000007$.

5
1 0
5 0
3 2
1 2
2 3
3 2
2 1
2 3
3 3
1 2
2 3
3 1

1
42
1
2
0

BestCoder Round #31