Foxling Feeding Frenzy

View as PDF

Submit solution

Points: 7
Time limit: 2.5s
Memory limit: 64M

Problem type
University of Toronto ACM-ICPC Tryouts 2012

You've come across N (1 \le N \le 200) adorable little Foxlings, and they're hungry! Luckily, you happen to have M (1 \le M \le 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 \le A_i \le B_i \le 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 \le T \le 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 Specification

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 \dots N

Output Specification

For each scenario:
Line 1: 1 integer, the number of valid cracker distributions modulo 10^9 + 7

Sample Input

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

Sample Output


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.


There are no comments at the moment.