Sticker

"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

• 写回答

1条回答默认 最新

• threenewbee 2017-09-03 14:30
关注
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

悬赏问题

• ¥20 基于python进行多背包问题的多值编码
• ¥15 相同型号电脑与配置，发现主板有一台貌似缺少了好多元器件似的，会影响稳定性和使用寿命吗？
• ¥15 要求编写稀疏矩阵A的转置矩阵的算法
• ¥15 编写满足以下要求的停车场管理程序，设停车场只有一个可停放n辆车的狭窄通道且只有一个大门可供车辆进出。
• ¥15 C语言：数据子序列基础版
• ¥20 powerbulider 导入excel文件，显示不完整
• ¥15 用keil调试程序保证结果进行led相关闪烁