"Shock You", a name of candy, which is new product of cc98. In fact, its selling point is the sticker inside. To collect different stickers, little children will buy it again and again.
The employees in cc98 are excellent. They have designed 3 kinds of stickers like this, this and this.
picture
But the manager thinks that it is not enough. To persuade his employees, He investigated the habits of some children about collecting.
In this district, a child called WuKe buys one bag of candies every day and gets one sticker inside. So in N days he can get N stickers. If cc98 has N kinds of stickers, he can collect all at least in N day. Unfortunately, it is nearly impossible because of duplicate ones.
But WuKe is not fool. Though duplicate ones are worthless to himself, he can exchange different stickers with others. There are M collectors in the district. To avoid unfair competition, these collectors need different stickers and what they offer are different too. That means, Wuke have to exchange some stickers indirectly.
As we know, if WuKe buys one candy every day, it is usually difficult to collect all N kinds of stickers in N days. But by exchanging, it becomes much easier.
Now the manager of cc98 wants to know how many different ways WuKe can do it.
Note: Different order is regarded as different ways. For instance, if N = 2 and WuKe can exchange 0 to 1, there are 3 ways. (0 0, 0 1 and 1 0)
Input
The first line is an integer C. Then C cases follow. There are no more than 100 cases.
For each case, the first line contains 2 integers N and M (1 ≤ M < N ≤200. Then there are M lines. Each line has 2 integer ai and bi (0 ≤ ai,bi < N), which means there is a collector want to exchange his/her sticker bi to your sticker ai.
Output
A single line contains an integer O indicates how many different ways. It may very large so that you can output O mod 1000000007.
Simple Input
2
2 1
0 1
5 3
0 1
1 2
3 4
Simple Output
3
480
