Rahat lives in a strange country. Name of the cities of this country are also strange. Instead of traditional naming, here, cities are named by number like 1, 2, 3 …..N. Cities are named according to their size. That is, city 1 is the smallest city, city 2 is 2^nd smallest…. city N is the largest city of the country.

People of the country are very concerned about traffic. To avoid collision and jam, every road is one directional. Rule of visiting from one city to another are:

• When visiting from a city to a larger city, you must have to journey through bus.
• When visiting from a city to a smaller city, you must have to journey through train.

Rahat lives in city 1. He wants to go in city N. As he likes journey very much, he wants to know, in how many ways he can complete his journey.

He dislikes riding on train. So he will not ride on train during his journey.

Input

Input set starts with an integer (T<=101), denoting the test case. Then T test case follows.

Each case starts with two integer (1 <= N <= 10^5, 0<=M<=MIN (10^5, (N*(N-1))/2)), where N denotes number of cities and M denotes number of roads in that city. Then M lines follow. Each line denotes two integers (1<= u, v <= N, u != v) which indicates there is a road between u and v for bus transportation.

Output

For each case, print total way Rahat can make to arrive on city N. As the answer can be very big, print the answer modulo 1000000007. For correct format, look at the sample output.

Example

Input:
1
4 3
1 2
2 3
3 4

Output:
Case 1: 1