World Cup Cricket 2011 is coming. Many of you may not be interested in cricket, but it's really a passion in our subcontinent. Ranking of cricketers is a common phenomenon there. Cricketers are ranked by their performance in both form of cricket (Test and One-day). People really enjoy this ranking. They like to see their favorite players as top ranked. Currently many such rankings are available. And as you have guessed, each ranking makes a different player as top ranked.
World Cup committee has decided that they will make a new ranking on the performance of players in the world cup. They want the ranking to be acceptable to the public. The rules are:
- There are K different departments. Cricketers will be given points in each department depending on their performance.
- The maximum points for each department are not equal. Such as Sakib Al Hasan can get maximum 25 points in batting but Mushfiqur Rahim can get maximum 10 points for his spectacular wicket keeping.
- The sum of maximum points of all departments will be exactly N points. And the final ranking will depend on the total earned points out of N points.
The ranking committee wants popular cricketers to get top ranked. To do so, they even allow maximum points for fielding more than that of batting. But that can bring lots of criticism. So they decide to fix a range of points for each department. Such as maximum points for batting will be at least 10 and at most 15 or for fielding, it will be at least 8 and at most 12. But the total points will be 20. Then 3 ranking systems are possible, such as: (10, 10), (11, 9) and (12, 8) for batting and fielding respectively. In this problem, you have to find the number of ranking systems possible for given number of departments, range of points for each department and total points.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a blank line and two integers K (1 ≤ K ≤ 10) and N (1 ≤ N ≤ 106). Each of the next K lines denotes the lower and upper limit of allowable maximum points for each department. These integers will be in the range [0, 106]. And the lower limit of each department will always be less than or equal to the upper limit of that department.
Output
For each case, print the case number and the number of rankings possible modulo 100000007.
Sample
| Sample Input | Sample Output |
|---|---|
4 4 10 1 1 2 2 3 3 4 4 4 10 1 1 2 2 3 3 3 3 2 10 1 10 1 10 2 20 10 15 8 12 | Case 1: 1 Case 2: 0 Case 3: 9 Case 4: 3 |