# Ira and Flamenco solution codeforces

## Ira and Flamenco solution codeforces

Ira loves Spanish flamenco dance very much. She decided to start her own dance studio and found 𝑛 students, 𝑖th of whom has level 𝑎𝑖��.

Ira can choose several of her students and set a dance with them. So she can set a huge number of dances, but she is only interested in magnificent dances. The dance is called magnificent if the following is true:

• exactly 𝑚 students participate in the dance;
• levels of all dancers are pairwise distinct;
• levels of any two dancers have an absolute difference strictly less than 𝑚.

For example, if 𝑚=3�=3 and 𝑎=[4,2,2,3,6]�=[4,2,2,3,6], the following dances are magnificent (students participating in the dance are highlighted in red): [4,2,2,3,6][4,2,2,3,6][4,2,2,3,6][4,2,2,3,6]. At the same time dances [4,2,2,3,6][4,2,2,3,6][4,2,2,3,6][4,2,2,3,6][4,2,2,3,6][4,2,2,3,6] are not magnificent.

In the dance [4,2,2,3,6][4,2,2,3,6] only 22 students participate, although 𝑚=3�=3.

The dance [4,2,2,3,6][4,2,2,3,6] involves students with levels 22 and 22, although levels of all dancers must be pairwise distinct.

In the dance [4,2,2,3,6][4,2,2,3,6] students with levels 33 and 66 participate, but |36|=3|3−6|=3, although 𝑚=3�=3.

Help Ira count the number of magnificent dances that she can set. Since this number can be very large, count it modulo 109+7109+7. Two dances are considered different if the sets of students participating in them are different.

Input

The first line contains a single integer 𝑡 (1𝑡1041≤�≤104) — number of testcases.

The first line of each testcase contains integers 𝑛 and 𝑚 (1𝑚𝑛21051≤�≤�≤2⋅105) — the number of Ira students and the number of dancers in the magnificent dance.

The second line of each testcase contains 𝑛 integers 𝑎1,𝑎2,,𝑎𝑛�1,�2,…,�� (1𝑎𝑖1091≤��≤109) — levels of students.

It is guaranteed that the sum of 𝑛 over all testcases does not exceed 21052⋅105.

## Ira and Flamenco solution codeforces

For each testcase, print a single integer — the number of magnificent dances. Since this number can be very large, print it modulo 109+7109+7.

Example
input

Copy
9
7 4
8 10 10 9 6 11 7
5 3
4 2 2 3 6
8 2
1 5 2 2 3 1 3 3
3 3
3 3 3
5 1
3 4 3 10 7
12 3
5 2 1 1 4 3 5 5 5 2 7 5
1 1
1
3 2
1 2 3
2 2
1 2
output

Copy
5
2
10
0
5
11
1
2
1

Note

In the first testcase, Ira can set such magnificent dances: [8,10,10,9,6,11,7][8,10,10,9,6,11,7][8,10,10,9,6,11,7][8,10,10,9,6,11,7][8,10,10,9,6,11,7][8,10,10,9,6,11,7][8,10,10,9,6,11,7][8,10,10,9,6,11,7][8,10,10,9,6,11,7][8,10,10,9,6,11,7].

The second testcase is explained in the statements.