P6522 [CEOI 2010] tower (day2)

The ancient Babylonians decided to build a tower.

The tower has a total of $n$ levels, and each level consists of one cubic stone block with side length $a_i$. A block $i$ can be placed directly on top of block $j$ if and only if $a_i \leq a_j + D$, where $D$ is a given constant. You need to find how many different building plans there are if all blocks are used. Output the result $\bmod\ 10^9+9$. **Note: Even if two blocks have the same side length, they are still considered different blocks.**

The first line contains two integers $n, D$. The second line contains $n$ integers $a_1, \dots, a_n$, representing the side lengths of the cubic stone blocks.

Output one line with one integer, the total number of plans $\bmod\ 10^9+9$.

#### Sample Explanation #### Sample 1 Explanation First, place the block with side length $100$ at the bottom. The remaining blocks can be placed in any order except for the following two cases: `2,1,3` and `1,3,2`. #### Sample 2 Explanation First, it is not allowed to place $20$ on top of $10$. So, put all the $20$ blocks as a stack at the bottom, and all the $10$ blocks as a stack on the top. That is $(3!)\times (3!) = 36$. #### Constraints - For $10\%$ of the testdata, $n \le 10$ is guaranteed; - For $30\%$ of the testdata, the number of plans does not exceed $10^6$; - For $45\%$ of the testdata, $n \le 20$ is guaranteed; - For $70\%$ of the testdata, $n \le 70$ is guaranteed; - For $100\%$ of the testdata, $2 \le n \le 6.2 \times 10^5$, and all numbers in the input are positive integers not exceeding $10^9$. #### Notes **This problem is translated from [CEOI 2010](http://ceoi2010.ics.upjs.sk/Contest/Tasks) day 2 *[T3 tower](https://people.ksp.sk/~misof/ceoi2010/tow-eng.pdf)***. The translation copyright belongs to the problem provider @[ShineEternal](https://www.luogu.com.cn/user/45475). Reproduction without permission is prohibited. Translated by ChatGPT 5