Sticker

Time Limit: 2 Seconds
Memory Limit: 65536 KB

*"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.

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 `a`_{i} and `b`_{i} (0 ≤ `a`_{i},`b`_{i} < `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

Author:

**HUANG, Minzhi**
Contest:

**ZOJ Monthly, September 2010**
Submit
Status