408797: GYM103325 A ВКОШП для юниоров

A. ВКОШП для юниоровограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

В этом году одна из школ запускает новую линейку командных олимпиад «ВКОШП-junior» для учеников 6-8 классов. Главная цель олимпиады — привлечение юных программистов и повышение интереса к олимпиадному движению. Тренеры стараются подобрать команды так, чтобы ребята чувствовали себя комфортно. Для этого сила любых двух участников команды должна отличаться не более чем на $$$с$$$ единиц силы. По правилам соревнования команды состоят из $$$k$$$ школьников. У тренера Славы на кружке $$$n$$$ школьников, пронумерованных числами от $$$1$$$ до $$$n$$$. Cила $$$i$$$-го школьника составляет $$$a_i$$$ единиц силы. Сколькими способами Слава может выбрать одну команду для участия во «ВКОШП-junior» с соблюдением вышеописанных условий?

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

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

В первой строке даны 3 целых числа $$$n$$$, $$$k$$$ и $$$c$$$ $$$(1 \le n \le 100\,000,\; 2 \le k \le n,\; 0 \le c \le 10^9)$$$ — число школьников, размер команды и значение максимального разброса силы соответственно.

Во второй строке даны целые числа $$$a_i$$$ $$$(0 \le a_i \le 10^9)$$$ — показатели силы школьников.

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

Выведите одно целое число — количество способов выбрать одну команду по модулю $$$10^9 + 7$$$.

Система оценки

$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \\ \hline 1 & 10 & k = 2, n \le 2000 & \text {}\\ \hline 2 & 16 & k = 2 & \text {1}\\ \hline 3 & 31 & n \le 2\,000 & \text {1}\\ \hline 4 & 17 & k \le 5 & \text {1, 2} \\ \hline 5 & 26 & \text { Нет дополнительных ограничений } &\text {1, 2, 3, 4}\\ \hline \end{array}$$$$$$

ПримерВходные данные

6 2 5
10 2 7 9 1 4

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

9

Примечание

Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.