Having dealt with most of the kingdoms on mainland Westeros, Daenerys turns to the Kingdom of Iron Islands.
The ruler, Balon Greyjoy proposes that he would not interfere in Daenerys' quest for the Iron Throne, if she succeeds in solving an engineering problem that they have been facing for many years in the Iron Islands.

They want to construct bridges between pairs of islands such that the following requirements are met:

All the islands are numbered from 1 to N, and M bridges have to be constructed,

There can be at-most one bridge between any pair of islands. (i.e the bridge network is a simple undirected graph),

All the islands are connected to each other (i.e there is a way to reach any island from every other island),

This network of islands must remain connected even after a particular island and all bridges incident on it are destroyed.

The bridges are constructed with supernatural powers, therefore destroying such a bridge merges the two islands, which were connected by it, into one larger island, and all the other bridges incident on the two islands are now
incident on the merged island. (This is exactly like the notion of edge-contraction in an undirected graph). In order to avoid displeasing the Drowned God whom the Ironborns worship, Balon Greyjoy wants the network of bridges designed in such a way that it should not be possible to convert the network into a cycle of 5 islands, by sequentially destroying some bridges.

The task at Daenerys' hand is to find the number of ways such a bridge network can be constructed (the number of possible graphs, treating the islands as distinct vertices and the bridges as undirected edges)

Input

The first line contains the number of test cases T. Each of the next lines contains two integers N and M.

Output

Output T lines, one corresponding to each test case. For a test case, output the number of possible bridge networks (graphs) as described in the question. Output the answer modulo 1000000007.

Constraints

1 ≤ T ≤ 2000

1 ≤ N ≤ 100

0 ≤ M ≤ 10000

SAMPLE INPUT
5
1 0
3 2
3 3
4 4
5 10

SAMPLE OUTPUT
1
0
1
3
0

见题面

见题面