## UOFTAE - Foxling Feeding Frenzy

You've come across $N$ ($1 \leq N \leq 200$) adorable little Foxlings, and they're hungry! Luckily, you happen to have $M$ ($1 \leq M \leq 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 \leq A_i \leq B_i \leq 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 \leq T \leq 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

First line: 1 integer, $T$

For each scenario:

First line: 2 integers, $N$ and $M$

Next $N$ lines: 2 integers, $A_i$ and $B_i$, for $i = 1..N$

### Output

For each scenario:

Line 1: 1 integer, the number of valid cracker distributions modulo $10^9+7$

### Example

Input:
22 51 42 63 52 22 92 3

Output:
30
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.

hide comments
 < Previous 1 2 Next > sherlock11: 2018-02-05 14:48:06 similar problem is BEHAPPY........... Sudarshan K: 2016-04-21 17:17:12 Screwed up the base case. Otherwise nice DP :) Use long long. raghav12345: 2016-01-29 17:21:57 yes a easy one but firstly took about 2 hr of time :( anshal dwivedi: 2016-01-05 21:36:25 Easy DP :) D: 2015-08-31 07:43:36 First do BEHAPPY if you are stuck on this. (it will help you to figure out the recurrence then apply memoization for this problem) Mayank Garg: 2015-08-15 16:39:45 AC in one go !! ...Abhinandan Agarwal _/\_.... your comments are always very helpful :p !! Keep guiding us .. :-) Well no negative crackers indeed !! :p Last edit: 2015-08-20 22:55:25 Abhinandan Agarwal: 2015-08-05 16:47:46 Do check for negative no. of crackers !!! mr_lazy: 2015-07-20 22:20:30 AC in one go! :D Aman Agarwal: 2015-06-22 18:31:38 same memoized code for BEHAPPY accepted here too..just changed to long long..as said by @Abhishek no need to worry about modulo .:frUstrAteD:.: 2015-02-16 17:24:03 AC without considering modulo.. :P

 Added by: SourSpinach Date: 2013-05-17 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: Own problem, used in the 2012 UofT ACM Tryouts