Stone Tower Construction

You are given n stone blocks. The i-th block is a cube with side length \(a_i\). You have to build a tower using all the stones (each stone is used exactly once) so that the resulting tower has n layers. In the tower, one block can be placed directly on top of another block if and only if the block above has side length at most \(a_j+D\), where \(a_j\) is the side length of the block immediately below and \(D\) is a given constant.

More formally, if the tower (from bottom to top) is represented by a permutation \(p_1,p_2,\dots,p_n\) of \(\{1,2,\dots,n\}\), then for every \(k=2,3,\dots,n\) the following condition must hold: \[ a_{p_k} \le a_{p_{k-1}} + D. \]

Note that even if two stones have the same side length, they are considered distinct. Your task is to count the number of different valid towers you can build using all the stones. Output the answer modulo \(10^9+9\).

inputFormat

The first line contains two integers \(n\) and \(D\) \((1 \le n \le 10^5,\ 0 \le D \le 10^9)\) representing the number of stones and the constant added to the lower stone's side length, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le 10^9)\) representing the side lengths of the stones.

outputFormat

Output a single integer, the number of valid tower constructions using all the stones, modulo \(10^9+9\).

sample

2 0
1 2

1