## Foxling Feeding Frenzy

View as PDF

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

Author:
Problem type
##### University of Toronto ACM-ICPC Tryouts 2012

You've come across adorable little Foxlings, and they're hungry! Luckily, you happen to have 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 must be fed at least crackers, or it will remain hungry, but no more than of them, or it will become hyper . 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 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 (as this value can be quite large).

#### Input Specification

Line 1: 1 integer,
For each scenario:
Line 1: 2 integers, and
Next lines: 2 integers, and , for

#### Output Specification

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

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