SP14974 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).

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 $

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