University of Toronto ACM-ICPC Tryouts 2012

You've come across ~N~ ~(1 \le N \le 200)~ adorable little Foxlings, and they're hungry! Luckily, you happen to have ~M~ ~(1 \le M \le 200)~ crackers on hand, and everyone knows that Foxen love crackers! You'd like to distribute all of your crackers, without splitting any of them, among the Foxlings - but you have to be careful. Foxling ~i~ must be fed at least ~A_i~ crackers, or it will remain hungry, but no more than ~B_i~ of them, or it will become hyper ~(1 \le A_i \le B_i \le 200)~. You certainly don't want any hungry or hyper Foxlings on your hands, and you're curious as to how many ways this can be accomplished.

There are ~T~ ~(1 \le T \le 100)~ scenarios as described above. For each one, you'd like to determine the number of different distributions of your crackers that would satisfy all of the Foxlings, modulo ~10^9 + 7~ (as this value can be quite large).

Input Specification

Line 1: 1 integer, ~T~
For each scenario:
Line 1: 2 integers, ~N~ and ~M~
Next ~N~ lines: 2 integers, ~A_i~ and ~B_i~, for ~i = 1 \dots N~

Output Specification

For each scenario:
Line 1: 1 integer, the number of valid cracker distributions modulo ~10^9 + 7~

Sample Input

2
2 5
1 4
2 6
3 5
2 2
2 9
2 3

Sample Output

3
0

Explanation of Sample

In the first scenario, you can give either 1, 2, or 3 crackers to the first Foxling, and the remaining 4, 3, or 2 (respectively) to the second.

In the second scenario, each Foxling must receive at least 2 crackers, while you only have 5 to give out, so you have no valid options.