거대한 탑

고대 바빌로니아 사람들이 거대한 탑을 쌓기로 했다. 이 탑은 정육면체 모양의 블록 $N$개를 하나씩 위로 쌓아 만든다. 그들은 나라 곳곳에서 다양한 크기의 블록을 많이 모았다. 예전에 실패했던 경험을 통해, 훨씬 작은 블록 위에 큰 블록을 바로 올리면 탑이 무너진다는 사실을 알게 되었다.

두 블록은 크기가 같더라도 서로 다른 것으로 본다. 각 블록의 한 변의 길이가 주어진다. 또한 정수 $D$가 주어지는데, 블록 $A$의 변의 길이가 블록 $B$의 변의 길이에 $D$를 더한 값보다 크면(엄밀히 큰 경우) 블록 $A$를 블록 $B$의 바로 위에 올릴 수 없다.

모든 블록을 사용하여 탑을 쌓는 서로 다른 방법의 수를 구하여라. 이 수가 매우 커질 수 있으므로, $10^9 + 9$로 나눈 나머지를 출력한다.

첫째 줄에 두 양의 정수 $N$과 $D$가 주어진다. 각각 블록의 개수와 허용 오차를 의미한다.

둘째 줄에는 공백으로 구분된 $N$개의 정수가 주어지며, 각 블록의 한 변의 길이를 나타낸다.

쌓을 수 있는 탑의 개수를 $10^9 + 9$로 나눈 나머지를 한 줄에 정수 하나로 출력한다.

입력에 주어지는 모든 수는 $10^9$ 이하의 양의 정수이다. $N$은 항상 $2$ 이상이다.