Маша работает в рекламном агентстве. В целях продвижения нового бренда она хочет заключить договор с некоторыми блогерами. Всего у Маши есть контакты \(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\).
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных следующие варианты являются подходящими:
- заключить договор с блогерами с номерами \(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\).