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.