Огромная башня
Древние вавилоняне решили построить огромную башню. Башня состоит из 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.