Codeforces Round 874 (Div. 3) |
---|
Закончено |
Ира очень любит испанский танец фламенко. Она решила основать собственную танцевальную студию и нашла $$$n$$$ учеников, $$$i$$$-й из которых имеет уровень $$$a_i$$$.
Ира может выбрать несколько своих учеников и поставить с ними танец. Таким образом она может поставить огромное количество танцев, но её интересуют только великолепные танцы. Танец называется великолепным, если выполнено следующее:
Например, если $$$m = 3$$$ и $$$a = [4, 2, 2, 3, 6]$$$, следующие танцы являются великолепными (красным цветом выделены ученики, участвующие в танце): $$$[\color{red}{4}, 2, \color{red}{2}, \color{red}{3}, 6]$$$, $$$[\color{red}{4}, \color{red}{2}, 2, \color{red}{3}, 6]$$$. В то же время танцы $$$[\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}]$$$ не являются великолепными.
В танце $$$[\color{red}{4}, 2, 2, \color{red}{3}, 6]$$$ участвуют $$$2$$$ ученика, хотя $$$m = 3$$$.
В танце $$$[4, \color{red}{2}, \color{red}{2}, \color{red}{3}, 6]$$$ участвуют ученики с уровнями $$$2$$$ и $$$2$$$, хотя уровни всех танцоров должны быть попарно различны.
В танце $$$[\color{red}{4}, 2, 2, \color{red}{3}, \color{red}{6}]$$$ участвуют ученики с уровнями $$$3$$$ и $$$6$$$, но $$$|3 - 6| = 3$$$, хотя $$$m = 3$$$.
Помогите Ире посчитать количество великолепных танцев, которые она может поставить. Так как это число может быть очень большим, посчитайте его по модулю $$$10^9 + 7$$$. Два танца считаются различными, если различны наборы учеников, участвующих в них.
В первой строке дано единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит целые числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le n \le 2 \cdot 10^5$$$) — количество учеников Иры и количество танцоров в великолепном танце.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — уровни учеников.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите единственное число — количество великолепных танцев по модулю $$$10^9 + 7$$$.
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
5 2 10 0 5 11 1 2 1
В первом наборе входных данных Ира может поставить только такие великолепные танцы: $$$[\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]$$$.
Второй набор входных данных разобран в условии.
Название |
---|