P6522 [CEOI 2010] tower (day2)

古巴比伦人决定建造一座塔。

这座塔共有 $n$ 层，每层由一个边长为 $a_i$ 的立方体石块构成。一个石块 $i$ 能够直接放在石块 $j$ 上当且仅当 $a_i \leq a_j+D$，其中 $D$ 为一个给定的常数。 你需要求出如果使用全部的石块，有多少种不同的搭建方案。输出答案 $\bmod\ 10^9+9$ 的结果。 **注意：即使两个石块的边长相同，也看做不同的石块。**

输入第一行两个整数 $n,D$。 第二行 $n$ 个整数 $a_1,\dots,a_n$，表示每个立方体石块的边长。

输出一行一个整数，表示方案总数 $\bmod\ 10^9+9$ 的结果。

#### 【样例解释】 #### 样例 1 解释 首先把边长为 $100$ 的石块放在底部，其余的石块可以任意顺序放置，除了以下两种情况：`2,1,3` `1,3,2`。 #### 样例 2 解释 首先不允许在 $10$ 上面放 $20$。 所以就把 $20$ 一堆放在底下，$10$ 一堆放在上面。 即 $(3!)\times (3!)=36$。 #### 【数据规模与约定】 - 对于 $10\%$ 的数据，保证 $n\le 10$； - 对于 $30\%$ 的数据，保证方案数不超过 $10^6$； - 对于 $45\%$ 的数据，保证 $n\le 20$； - 对于 $70\%$ 的数据，保证 $n\le 70$； - 对于 $100\%$ 的数据，保证 $2\le n\le 6.2\times 10^5$，输入中所有数字为不超过 $10^9$ 的正整数。 #### 【说明】 **题目译自 [CEOI 2010](http://ceoi2010.ics.upjs.sk/Contest/Tasks) day 2 *[T3 tower](https://people.ksp.sk/~misof/ceoi2010/tow-eng.pdf)***。 翻译版权为题目提供者 @[ShineEternal](https://www.luogu.com.cn/user/45475) 所有，未经许可禁止转载。