Connect kingdom has N cities numbered 1 through N. Each city has a train station. Of course every train station is connected to all the other train stations. People in the connect kingdom build a unique, bi-directional rail route for each of these connections. One of the good sides of this system is that if some connections are out of order, they seldom becomes an issue because you can always nd a substitute route easily. Also the people are actively keeping those connections working. Based on a technical report, it's guaranteed that there is at most one broken connection connected to any single train station!
The rail network is famous because there are many different routes to take and many di erent sceneries to see. Kirito is planning a train tour in the connect kingdom. Kirito will arrive at an arbitrarily city c0 on the first day by air. Then for each day of the following K days, he will take a train to a new city c that c > c0 and he has not visited c in this tour yet. On the last ((K +2)th) day he'll take a train from where he is to city c0 to catch the returning plane.
Kirito wants to visit at least 3 di erent cities, i.e. K ≥ 2, and he also wants to make sure every rail connection in the planned tour is not broken. Kirito knows the list of broken rail connections and he would like to know the number of di erent possible tours under these constraints.
He takes this question to his friend, Shinon, and ask if she can compute the number for him since Shinon is good at math (she's good at paintball too, btw). Shinon is so good at math so she proved that no matter which set of connections are broken, the number will be the same as long as the amount of broken connections is the same. Shinon's discovery simplified the problem a lot but the proof took Shinon so long that she doesn't have time to compute the number because she has to attend the International Contest of Paintball Championship. So once again it's your task to nd the number given the amount of broken rail connections. The number might be large, please mod it by 1,000,000,007.
Two tours are different if and only if K is di erent among the two tours or there is at least one day that Kirito visits di erent cities in two tours.
The first line of the input data contains an integer T (1 ≤ T ≤ 10200) specifying the number of test cases.
The first and single line of each test case contains two integers N and M (3 ≤ N ≤ 200, 0 ≤ M ≤ N/2) indicating the number of cities and the amount of broken connections.
For each test case, output a single line containing the number of possible highest score.