C. Мусор

Дед Олег поссорился со своим соседом Фёдором. Решив просто так не сдаваться, Олег задумал диверсию – набросать своему соседу под забор мусора.

Олег не хочет мусорить абы где, поэтому он выделил N точек вдоль забора Фёдора (забор длинный, поэтому его можно считать просто прямой линией), в которых он может намусорить. У Олега хватает мусора, чтобы набросать его в K различных точках, причём он хочет, чтобы разных куч мусора было ровно K.

Олегу не чуждо чувство прекрасного, поэтому он не хочет, чтобы расстояние между двумя любыми кучами мусора было меньше R. Олег не хочет ограничиваться одним разом, поэтому он каждую ночь решил приходить к забору своего соседа и мусорить. Однако чтобы его не заподозрили, Олег решил каждый день раскидывать мусор по-разному (два способа различны, если существует хотя бы одна точка, в которой в первом способе есть мусор, а во втором нет).

Олега интересует, сколько дней он сможет таким образом донимать своего соседа. Так как ответ может быть очень большим (Олег весьма изобретателен), он просит вас посчитать это число по модулю 10⁹+7.

Формат входного файла

Первая строка входного файла содержит три целых числа N, K и R (1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 50 1 ≤ R ≤ 10⁹) – количество точек для мусора, количество куч, которые хочет сделать Олег и минимальное расстояние между замусоренными точками, соответственно. Вторая строка входного файла содержит N целых чисел 0 ≤ d_i ≤ 10⁹ – расстояние до i-й точки от начала забора, все расстояния различны.

Формат выходного файла

В выходной файл выведите единственное число – ответ по модулю 10⁹ + 7.

Пример:

Источник: Открытый зимний чемпионат ПетрГУ по программированию, 15 декабря 2013

Обсудить       Отправить решение



Версия для печати