Time Limit : 10 Second

Memory Limit : 128 MB

Submission: 469

Solved: 109

Description





Halloween is coming! So xiaoY has to prepare M candies to treat the neighbor kids.



When this horrible night come, There are N little children ask xiaoY for candy, and each of them has different demand. For the i-th kid, his (or her) candy must not less than Min[i], and not greater than Max[i].



 



Now xiaoY wants to know how many ways he can give out all of his candies. (in case the large answer, please tell xiaoY the answer modular 10000007)


Input





First line is an integer T, represents T cases followed:



N, M ---- Number of children, Number of candies.



(0<N<=20, 0<M<=10000)



Min[i], Max[i] ---- The lower bound and upper bound of I-th kid’s demand. (N lines)



(0<=Min[i] <= Max[i] <=M)


Output


Output a number W which means total different ways of handing out the candies. (% 10000007)


sample input
2
3 5
1 2
1 2
1 2
3 6
1 2
1 2
1 2
sample output
Case #1: 3
Case #2: 1
hint

For case 1, there are 3 ways to hand out:

1 + 2 + 2 = 5

2 + 1 + 2 = 5

2 + 2 + 1 = 5

For case 2, there is only one way to hand out:

2 + 2 + 2 = 6

source
© 2015 HUST ACMICPC TEAM. All Right Reserved.