### 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`of them, or it will become hyper (1 ≤

_{i}`≤`

`A`_{i}`B`≤ 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.

_{i}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^{9} + 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`, for

_{i}`i`= 1..

`N`

### Output

For each scenario:

Line 1: 1 integer, the number of valid cracker distributions modulo 10^{9} + 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)

ImaxBlueon Mar 17, 2015 - 2:29:43 pm UTC sample datajargonon Mar 17, 2015 - 5:29:23 pm UTC Re: sample dataBe careful not to skip over the line containing N and M!