## UOFTAE - Foxling Feeding Frenzy

You've come across N (1N2001≤�≤200) adorable little Foxlings, and they're hungry! Luckily, you happen to have M (1M2001≤�≤200) 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 i must be fed at least Ai�� crackers, or it will remain hungry, but no more than Bi�� of them, or it will become hyper (1AiBi2001≤��≤��≤200). 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 T (1T1001≤�≤100) 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 109+7109+7 (as this value can be quite large).

### Input

First line: 1 integer, T

For each scenario:

First line: 2 integers, N and M

Next N lines: 2 integers, Ai�� and Bi��, for i=1..N�=1..�

### Output

For each scenario:

Line 1: 1 integer, the number of valid cracker distributions modulo 109+7109+7

### Example

Input:
22 51 42 63 52 22 92 3

Output:
30

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

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAXN = 2e2+5;

int n, m;
int A[MAXN], B[MAXN];
int dp[MAXN][MAXN];

ll solve(int idx, int left){
if(left < 0)	return 0;
if(idx == 0){
if(left >= A[0] && left <= B[0])	return 1LL;
else	return 0LL;
}
if(dp[idx][left] != -1)
return dp[idx][left];
ll res = 0;
for(int i = A[idx]; i <= B[idx]; i++){
res += solve(idx - 1, left - i);
res %= MOD;
}
return dp[idx][left] = res;
}

int main(){
io;
int t;
cin >> t;
while(t--){
memset(dp, -1, sizeof dp);
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> A[i] >> B[i];
cout << solve(n-1, m) << endl;
}
return 0;
}
Copy The Code &

Input

cmd
2
2 5
1 4
2 6
3 5
2 2
2 9
2 3

Output

cmd
3
0