Harry Potter and Ronald Weasley were playing a strange Snakes and Ladders game which did not consist of any Snakes, maybe because they don't like Snakes (Well anything can happen in the world of MAGIC). But unfortunately they didn’t have a dice. So, they were forced to move their pieces only one step forward. Ron, having lost his patience on playing this slow game challenged Harry for a duel to decide the winner.

Hermoine (the clever girl she is) broke the duel and asked Ron to tell her the total number of ways in which he could have reached the end starting from 1 (only forward jumps of 1 are allowed). If he gave the right answer, he would be considered a Winner otherwise not. Now your task is to help Ron find the correct answer.

NOTE : The board is not of square shape as in the actual game and the ladder can go from any lower point to any higher point. When encountering a ladder, the player has the choice of moving the piece up the ladder or to move one step forward.

At max 1 ladder can originate from a cell but more than 1 can end at a cell.

Input

First line of input would consist of an integer T specifying the number of test cases.

For each test case, first line would specify an integer representing N the total number of steps i.e. the end point of the board game.

Second line would consist of an integer L specifying the number of ladders.

The next l lines would consist of 2 space separated integers x and y (x < y) giving the source and destination points of the ladders.

Output

For each test case you have to output one line containing "Case #z: ans" (quotes for clarity) where z is the test case number starting from 1 and ans is the the answer to the question Hermoine asked Ron, given the board game configuration for the corresponding test case. Since the answer can be very large, print the answer modulo 10^9+7.

Constraints

1 <= N <= 10^5
0 <= L < N
0 <= x < y <= N

Example

Input:
1
3
2
1 3
2 3

Output:
Case #1: 3