Chain Heating

Time Limit: 3 Seconds    Memory Limit: 131072 KB

Nowadays, most of the electronic devices are enhanced with different kind of sensors to sense their surrounding environment. Recently, a company which works on house heating devices, has announced a new heating system based on heat sensor. This system consists of several little identical devices called “Heat Spot” which are capable of heating the environment around in a limited range called “Heat Range” and must be installed in different positions on the walls of a house to work well. The interesting thing about these little heat spots is that they are enhanced with heat sensor and can be activated by heating. Therefore if a heat spot A places in the heat range of heat spot B, activating heat spot B results in automatic activation of heat spot A. This process can cause an automatic chain activation of heat spots according to their relative positions and heat ranges. Figure 1 shows an example of heat spot arrangement on the wall of a house with corresponding heat ranges.

In this example by manually activating heat spots h₀ and h₂, all other heat spots will be activated automatically because of their heat sensor and their positions. Milad has bought this system for his new house and installed the heat spots in different positions on the wall. He wants to know in how many ways it is possible to activate all the heat spots by manually activating the minimum possible number of heat spots. For instance if he arranges the heat spots as the ones in figure 1, the available ways are first activating h₀ and second activating h₂ or first activating h­₂ and then activating h₀. Therefore, there are two ways to activate all the heat spots with minimum number of manual activations. Write a program to compute number of different ways to activate all the heat spots in an arrangement with minimum number of manual activations modulo 10⁹ + 7.

Input

First line of the input contains an integer N which is number of test cases. Each test case starts with a blank line following with a line containing two space separated integers n (1 <= n <= 1000) denoting number of heat spots and m. Each of the next m lines contains two space separated integers a and b denoting that heat spot a can activate heat spot b. Heat spots are numbered from 0 to n - 1.

Output

For each test case, print a line containing number of different ways to activate all the heat spots in a way the problem wants.

Sample Input

3

4 2
0 1
2 3

3 3
0 1
1 2
2 0

6 6
0 1
1 0
2 3
3 2
4 5
5 4

Sample Output

2
3
48

Submit