## 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 Ai crackers, or it will remain hungry, but no more than Bi of them, or it will become hyper (1 ≤ AiBi ≤ 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 109 + 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, Ai and Bi, for i = 1..N

### Output

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

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

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

Point Value: 15
Time Limit: 5.00s
Memory Limit: 64M
Author: SourSpinach

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