E. Рекламное агентство
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маша работает в рекламном агентстве. В целях продвижения нового бренда она хочет заключить договор с некоторыми блогерами. Всего у Маши есть контакты $$$n$$$ разных блогеров. Блогер с номером $$$i$$$ имеет $$$a_i$$$ подписчиков.

Так как бюджет у Маши ограничен, она может заключить договор только с $$$k$$$ разными блогерами. Конечно же, Маша хочет, чтобы ее рекламу увидело как можно больше людей. Поэтому она должна нанять блогеров с максимальным суммарным количеством подписчиков.

Помогите ей, найдите количество способов выбрать $$$k$$$ блогеров так, чтобы суммарное количество их подписчиков было максимально. Два способа считаются разными, если в первом способе есть хотя бы один блогер, которого нет во втором способе. Маша считает, что у всех блогеров разная аудитория (то есть не существует подписчика, который был бы подписан на двух разных блогеров).

Например, если $$$n=4$$$, $$$k=3$$$, $$$a=[1, 3, 1, 2]$$$, то у Маши есть два способа выбрать $$$3$$$-х блогеров с максимальным суммарным количеством подписчиков:

  • заключить договор с блогерами с номерами $$$1$$$, $$$2$$$ и $$$4$$$. В таком случае количество подписчиков будет равно $$$a_1 + a_2 + a_4 = 6$$$.
  • заключить договор с блогерами с номерами $$$2$$$, $$$3$$$ и $$$4$$$. В таком случае количество подписчиков будет равно $$$a_2 + a_3 + a_4 = 6$$$.

Так как ответ может быть достаточно большим, выведите его по модулю $$$10^9+7$$$.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 1000$$$) — количество блогеров и со сколькими из них можно подписать договор.

Во второй строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$a_1, a_2, \ldots a_n$$$ ($$$1 \le a_i \le n$$$) — количества подписчиков у блогеров.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите одно целое число — количество способов выбрать $$$k$$$ блогеров так, чтобы суммарное количество их подписчиков было максимально.

Пример
Входные данные
3
4 3
1 3 1 2
4 2
1 1 1 1
2 1
1 2
Выходные данные
2
6
1
Примечание

Первый набор входных данных разобран в условии.

Во втором наборе входных данных следующие варианты являются подходящими:

  • заключить договор с блогерами с номерами $$$1$$$ и $$$2$$$. В таком случае количество подписчиков будет равно $$$a_1 + a_2 = 2$$$;
  • заключить договор с блогерами с номерами $$$1$$$ и $$$3$$$. В таком случае количество подписчиков будет равно $$$a_1 + a_3 = 2$$$;
  • заключить договор с блогерами с номерами $$$1$$$ и $$$4$$$. В таком случае количество подписчиков будет равно $$$a_1 + a_4 = 2$$$;
  • заключить договор с блогерами с номерами $$$2$$$ и $$$3$$$. В таком случае количество подписчиков будет равно $$$a_2 + a_3 = 2$$$;
  • заключить договор с блогерами с номерами $$$2$$$ и $$$4$$$. В таком случае количество подписчиков будет равно $$$a_2 + a_4 = 2$$$;
  • заключить договор с блогерами с номерами $$$3$$$ и $$$4$$$. В таком случае количество подписчиков будет равно $$$a_3 + a_4 = 2$$$.

В третьем наборе входных данных следующие варианты являются подходящими:

  • заключить договор с блогера с номером $$$2$$$. В таком случае количество подписчиков будет равно $$$a_2 = 2$$$.