Хмарочос#11818

Хмарочос

1 секунда

128 мегабайтів

Дуже складна

Міжнародна олімпіада з інформатики відбудеться в місті Цукуба, Японія. У рамках підготовки до IOI ми плануємо побудувати хмарочоси на головній вулиці Цукуби. Оскільки ми хочемо створити нову визначну пам'ятку, будівлі повинні задовольняти наступним умовам.

Ми плануємо побудувати $n$ будівель вздовж прямої лінії на головній вулиці. Їх висоти задані числами $a_{1}, a_{2}, a_{3}, ..., a_{n}$ a_1, a_2, a_3, ..., a_n. Усі висоти різні. Оскільки порядок розташування будівель ще не визначений, ми можемо переставляти їх у будь-якому порядку. Будівлі будуть оздоблені до IOI. Проте через обмеження на використовувані матеріали, сума модулів різниць висот двох сусідніх будівель не повинна перевищувати $L$ . Іншими словами, якщо висоти будівель з одного боку вулиці позначити як $f_{1}, f_{2}, f_{3}, ..., f_{n}$ f_1, f_2, f_3, ..., f_n, то повинна виконуватись нерівність:

∣ f_{1} - f_{2} ∣ + ∣ f_{2} - f_{3} ∣ + ... + ∣ f_{n - 1} - f_{n} ∣ \leq L

|f_1 - f_2| + |f_2 - f_3| + ... + |f_{n-1} - f_n| \le L

Тут $∣ x ∣$ означає модуль числа $x$ .

Скільки існує таких перестановок будівель, які задовольняють зазначену умову?

За заданою кількістю будівель $n$ , їх висотами та обмеженням $L$ на суму модулів різниць висот сусідніх будівель, напишіть програму, яка обчислює кількість допустимих перестановок будівель. Оскільки відповідь може бути дуже великою, виведіть залишок від ділення цієї кількості на $1000000007$ .

Вхідні дані

Прочитайте наступні дані зі стандартного вводу.

Перша строка містить два цілих числа $n$ та $L$ $(1 \leq n \leq 100, 1 \leq L \leq 1000)$ (1 \le n \le 100, 1 \le L \le 1000) — кількість будівель та верхнє обмеження на суму модулів різниць висот сусідніх будівель.
Друга строка містить $n$ цілих чисел $a_{1}, a_{2}, a_{3}, ..., a_{n}$ a_1, a_2, a_3, ..., a_n $(1 \leq a_{i} \leq 1000$ (1 \le a_i \le 1000 $(1 \leq i \leq n)$ (1 \le i \le n), $a_{i} \neq = a_{j}$ a_i \ne a_j $(1 \leq i < j \leq n))$ (1 \le i < j \le n)) — висоти будівель.

Вихідні дані

Виведіть одне число — залишок від ділення кількості допустимих перестановок будівель на $1000000007$ .

Приклади

Приклад 1

Приклад 2

Примітка

Підзадача 1 [5 балів]: $n \leq 8$ n \le 8.

Підзадача 2 [15 балів]: $n \leq 14, L \leq 100$ n \le 14, L \le 100.

Підзадача 3 [80 балів]: Немає додаткових обмежень.