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
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

Abhishek: 2014-12-16 16:11:33

no need to worry about range overflows ,the answer fits within long long int in C++ , just dont forget to
cout << ans % 1000000007 ;


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