MOVIFAN - Movie Fan

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

For test case 1, Alice can watch 1 show in 3 ways, 2 shows in 3 ways and 3 show in 1 way total ways = 7.

For test case 3, Alice can watch 1 show in 3 ways, 2 shows in 2 ways, total ways = 5.


Added by:Umesh Malhotra
Date:2016-11-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2017-04-18 21:45:42
start times seem to be given in sorted order, and are smaller than 10^6
2016-11-22 11:33:20 Chinmay Kousik
Solve ACTIV after this
2016-11-16 16:42:34 Vipul Srivastava
Constraints on start times??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.