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
2020-06-07 21:44:04
Very good problem! Memoisation got AC with no problem.
2020-04-04 00:12:48
dam! dead easy
2018-10-17 19:26:19
just be careful you were reading extra input (0 0 ) incase you are doing it after BEHAPPY...
2018-06-11 00:27:15
Easy One! :P
2018-02-05 14:48:06
similar problem is BEHAPPY...........
2016-04-21 17:17:12 Sudarshan K
Screwed up the base case. Otherwise nice DP :) Use long long.
2016-01-29 17:21:57
yes a easy one but firstly took about 2 hr of time :(
2016-01-05 21:36:25 anshal dwivedi
Easy DP :)
2015-08-31 07:43:36 D
First do BEHAPPY if you are stuck on this. (it will help you to figure out the recurrence then apply memoization for this problem)
2015-08-15 16:39:45 Mayank Garg
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.