N ports are to be constructed on the bytelandian river. Since trade occurs only along a Y miles stretch of the river, the distance between the start point and the last port must be Y. (Consider start point has the 0th port.)

To optimize the ship movement between important ports, the distance between any two consecutive ports has been fixed to be within a range of possible distances. Also, distance between two consecutive ports can only be an integer number of miles.

As a programmer you have been assigned the job of evaluating the number of different possible arrangements of ports modulo 1000000007.

Input

First line of input contains t. The number of test cases (t < 100).

First line of each test case contains two integers: N, the number of ports to be built (N <= 20) and Y, the distance between the start point and the last port. (Y < 100000)

Next N lines of the test case contains the range of distances between consecutive ports, with ith line giving two integers, the minimum and maximum gap between (i-1)th and ith port.

Output

Print one of output for each test case which is the number of possible arrangements modulo 1000000007.

Example

Input:
1
2 4
0 3
0 3

Output:
3