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₁ cookies of the first type for the first friend, then he will make q₂ 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⁹ + 7.

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)

For each case, output the number of ways, modulo 10⁹ + 7.

1
3 1
4 3
2 2
2 1

15