Codeforces Round 874 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

constructive algorithms

data structures

implementation

math

sortings

two pointers

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Ira and Flamenco

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIra loves Spanish flamenco dance very much. She decided to start her own dance studio and found $$$n$$$ students, $$$i$$$th of whom has level $$$a_i$$$.

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 $$$m$$$ students participate in the dance;
- levels of all dancers are pairwise distinct;
- levels of every two dancers have an absolute difference strictly less than $$$m$$$.

For example, if $$$m = 3$$$ and $$$a = [4, 2, 2, 3, 6]$$$, the following dances are magnificent (students participating in the dance are highlighted in red): $$$[\color{red}{4}, 2, \color{red}{2}, \color{red}{3}, 6]$$$, $$$[\color{red}{4}, \color{red}{2}, 2, \color{red}{3}, 6]$$$. At the same time dances $$$[\color{red}{4}, 2, 2, \color{red}{3}, 6]$$$, $$$[4, \color{red}{2}, \color{red}{2}, \color{red}{3}, 6]$$$, $$$[\color{red}{4}, 2, 2, \color{red}{3}, \color{red}{6}]$$$ are not magnificent.

In the dance $$$[\color{red}{4}, 2, 2, \color{red}{3}, 6]$$$ only $$$2$$$ students participate, although $$$m = 3$$$.

The dance $$$[4, \color{red}{2}, \color{red}{2}, \color{red}{3}, 6]$$$ involves students with levels $$$2$$$ and $$$2$$$, although levels of all dancers must be pairwise distinct.

In the dance $$$[\color{red}{4}, 2, 2, \color{red}{3}, \color{red}{6}]$$$ students with levels $$$3$$$ and $$$6$$$ participate, but $$$|3 - 6| = 3$$$, although $$$m = 3$$$.

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

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of testcases.

The first line of each testcase contains integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 2 \cdot 10^5$$$) — the number of Ira students and the number of dancers in the magnificent dance.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — levels of students.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

Output

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

Example

Input

97 48 10 10 9 6 11 75 34 2 2 3 68 21 5 2 2 3 1 3 33 33 3 35 13 4 3 10 712 35 2 1 1 4 3 5 5 5 2 7 51 113 21 2 32 21 2

Output

5 2 10 0 5 11 1 2 1

Note

In the first testcase, Ira can set such magnificent dances: $$$[\color{red}{8}, 10, 10, \color{red}{9}, \color{red}{6}, 11, \color{red}{7}]$$$, $$$[\color{red}{8}, \color{red}{10}, 10, \color{red}{9}, 6, 11, \color{red}{7}]$$$, $$$[\color{red}{8}, 10, \color{red}{10}, \color{red}{9}, 6, 11, \color{red}{7}]$$$, $$$[\color{red}{8}, 10, \color{red}{10}, \color{red}{9}, 6, \color{red}{11}, 7]$$$, $$$[\color{red}{8}, \color{red}{10}, 10, \color{red}{9}, 6, \color{red}{11}, 7]$$$.

The second testcase is explained in the statements.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 20:30:38 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|