## MOVIFAN - Movie Fan

no tags

Alice is a cinephile. She wanted to watch a recently released movie. There are many movie shows whose start time and length are given. Your task is to help Alice count the number of ways she can watch the movie. Since she is a cinephile, she can watch many shows as long as they do not overlap.

### Input

First line contains an integer t denoting the number of test cases.

Each test case contains n, l denoting number of shows and length of the shows.

n integer follows denoting start time of each show.

1 <= t <= 10

1 <= n, l <= 300000

### Output

Print the number of ways Alice can watch shows if she wants to watch at least one show modulo 1000000007.

### Example

```Input:
3
3 4
3 8 12
3 1
1 2 3
3 3
3 5 9

Output:
7
7
5```

## 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 = 3e5+5;

ll st[MAXN], dp[MAXN], cum[MAXN];

int main(){
io;
int t;
cin >> t;
while(t--){
int n, l;
cin >> n >> l;
memset(dp, 0, sizeof dp);
memset(cum, 0, sizeof cum);
for(int i = 1;i <= n; i++)
cin >> st[i];
sort(st, st+n+1);
int k = 1;
ll ans = 0;
for(int i = 1;i <= n; i++){
while(k <= i && st[k] + l <= st[i])
k++;
dp[i] = (cum[k-1] + 1) % MOD;
cum[i] = (cum[i-1] + dp[i]) % MOD;
// cout << i << " " << cum[i] << " " << dp[i] << endl;
ans = (ans + dp[i]) % MOD;
}
cout << ans << endl;
}
return 0;
}``````
Copy The Code &

Input

cmd
3
3 4
3 8 12
3 1
1 2 3
3 3
3 5 9

Output

cmd
7
7
5