1708  Cookies
Time Limit : 2 Second
Memory Limit : 128 MB
Submission: 7
Solved: 2
 Description
Nero loves cookies. One day he invites N friends for dinner and he wants to make N types of cookies for them. At first, he will make q_{1} cookies of the first type for the first friend, then he will make q_{2} cookies of the second type for the second friend, and so on. It takes exactly one second for Nero to make a cookie. After making a cookie, Nero may be hungry and eat it immediately.(Consider eating a cookie doesn’t cost time) But he never eat two cookies in any consecutive (t + 1) seconds. Now it is known that the ith friend will be happy if he receives at least x_{i} cookies. How many ways can Nero make cookies while eating them to make all his friends happy? The answer may be very huge, so you have to calculate it modulo 10^{9} + 7.
 Input
The first line of the input contains an integer T (T=20), denoting the number of test cases.
In each test case, the first line of the input contains two integers N and t. Each of the next N lines contains two integers q_{i} and x_{i}. (1 ≤ n ≤ 1000; 0 ≤ t ≤ 100; 1 ≤ q_{i} ≤ 250; 0 ≤ x_{i} ≤ q_{i}) Output
For each case, output the number of ways, modulo 10^{9} + 7.
 sample input

1 3 1 4 3 2 2 2 1
 sample output

15
 hint
 source
 yangyue