BPORT - Building Ports

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

Added by:P != NP
Date:2010-10-22
Time limit:0.308s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP CPP14 C99 JAVA PAS-GPC PAS-FPC PYTHON
Resource:MNNIT IOPC 2010

hide comments
2010-11-25 03:45:43 [Rampage] Blue.Mary
O(K*Y) CAN get Accepted, but you need to do some constant optimization.
2010-11-24 10:24:57 :D
Is O(K*Y) enough for this problem?
2010-10-26 14:52:15 P != NP
problem updated. sorry for the inconvenience.
2010-10-26 14:52:15 Mostafa El-Sheikh
and How can Y = 4 when the max gap between both ports is 3 ? can anyone plz explain ?
2010-10-26 14:52:15 Mostafa El-Sheikh
How does the input state that the next (N-1) lines when in the sample input N lines are given ?!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.