Велика Вежа
Стародавні вавилоняни вирішили звести величезну вежу. Вежа складається з N кубічних будівельних блоків, які розміщуються один на одному. Вавилоняни зібрали багато блоків різних розмірів з усієї країни. З їхньої останньої невдалої спроби вони зрозуміли, що якщо покласти великий блок безпосередньо на значно менший, вежа впаде.
Кожен будівельний блок унікальний, навіть якщо його розмір такий самий, як у іншого. Для кожного блоку вам надано його довжину сторони. Також задано ціле число D, яке означає, що не можна класти блок A безпосередньо на блок B, якщо довжина сторони A строго більша за D плюс довжина сторони B.
Вам потрібно обчислити кількість різних способів, якими можна побудувати вежу, використовуючи всі будівельні блоки. Оскільки це число може бути дуже великим, виведіть результат за модулем 10^9+9.
Вхідні дані
Перша строка вхідних даних містить два додатні цілі числа N та D: кількість будівельних блоків та допустиму різницю відповідно.
Друга строка містить N цілих чисел, розділених пробілами; кожне представляє розмір одного будівельного блоку.
Обмеження
Усі числа у вхідних файлах є додатніми цілими числами, що не перевищують 10^9.
N завжди не менше 2.
У тестових випадках, що варті 70 балів, N буде не більше 70.
З них, у тестових випадках, що варті 45 балів, N буде не більше 20.
З них, у тестових випадках, що варті 10 балів, N буде не більше 10.
Для деяких тестових випадків загальна кількість допустимих веж не перевищуватиме 1000000. Ці тестові випадки варті 30 балів загалом.
Для останніх шести тестових випадків (вартістю 30 балів) значення N більше ніж 70. Верхня межа для N не задана для цих тестових випадків.
Вихідні дані
Виведіть один рядок, що містить одне ціле число: кількість веж, які можна побудувати, за модулем 1000000009.