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:
2
2 5
1 4
2 6
3 5
2 2
2 9
2 3
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.
hide comments
sherlock11:
20180205 14:48:06
similar problem is BEHAPPY...........


Sudarshan K:
20160421 17:17:12
Screwed up the base case. Otherwise nice DP :) Use long long. 

raghav12345:
20160129 17:21:57
yes a easy one but firstly took about 2 hr of time :( 

anshal dwivedi:
20160105 21:36:25
Easy DP :)


D:
20150831 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:
20150815 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: 20150820 22:55:25 

Abhinandan Agarwal:
20150805 16:47:46
Do check for negative no. of crackers !!! 

mr_lazy:
20150720 22:20:30
AC in one go! :D 

Aman Agarwal:
20150622 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:.:
20150216 17:24:03
AC without considering modulo.. :P

Added by:  SourSpinach 
Date:  20130517 
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 