University of Toronto ACM-ICPC Tryouts 2012

E: Foxling Feeding Frenzy

You've come across N (1 ≤ N ≤ 200) adorable little Foxlings, and they're hungry! Luckily, you happen to have M (1 ≤ M ≤ 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 ≤ A_i ≤ B_i ≤ 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 ≤ T ≤ 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⁹ + 7 (as this value can be quite large).

Input

Line 1: 1 integer, T
For each scenario:
Line 1: 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⁹ + 7

Sample Input

2
2 5
1 4
2 6
3 5
2 2
2 9
2 3

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

All Submissions
Best Solutions

Point Value: 15
Time Limit: 5.00s
Memory Limit: 64M
Added: Oct 02, 2012
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

idk pls downvote this

shouldn't the explanation for scenario 1 be that you can give 2, 3, or 4 to fox #1 and 3, 2, 1 respectively to #2

#1 needs 1-4 crackers, and #2 needs 2-6. If you give #1 four crackers, then #2 can only have one, and will go hungry.

Be careful not to skip over the line containing N and M!