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.


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

hide comments
2015-08-05 16:47:46 Abhinandan Agarwal
Do check for negative no. of crackers !!!
2015-07-20 22:20:30
AC in one go! :D
2015-06-22 18:31:38 Aman Agarwal
same memoized code for BEHAPPY accepted here too..just changed to long long..as said by @Abhishek no need to worry about modulo
2015-02-16 17:24:03 .:frUstrAteD:.
AC without considering modulo.. :P
2014-12-16 16:11:33 Abhishek
no need to worry about range overflows ,the answer fits within long long int in C++ , just dont forget to
cout << ans % 1000000007 ;
2014-10-07 19:46:25 NOVICE
done BEHAPPY ,but getting WA here !
2014-07-05 13:43:49 Sushantkumar M
Same problem as
http://www.spoj.com/problems/BEHAPPY/

RE: Thanks for pointing that out! That problem is older, but it also has smaller bounds and can apparently be solved with just recursion... so I think both should be kept in Classical.

Last edit: 2014-07-08 15:02:18
2014-04-06 08:46:43 Bharath Reddy
Beware of negative remainders.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.