高塔 ### 题目描述 要建造一栋 $n$ 层的塔，每层由一个边长为 $a_i$ 的立方体石块构成。一个石块 $i$ 能够直接放在石块 $j$ 上当且仅当 $a_i \leq a_j+D$，其中 $D$ 为一个给定的常数。 你需要求出如果使用全部的石块，有多少种不同的搭建方案。输出答案 $\bmod\ 10^9+9$ 的结果。 注意：即使两个石块的边长相同，也看做不同的石块。 ### 输入描述 输入第一行两个整数 $n,D$。 第二行 $n$ 个整数 $a_1,\dots,a_n$，表示每个立方体石块的边长。 其中，$2\le n\le 6.2\times 10^5$，输入中所有数字为不超过 $10^9$ 的正整数。 ### 输出描述 输出一行一个整数，表示方案总数 $\bmod\ 10^9+9$ 的结果。 ### 输入输出样例 #### 示例 1 >输入 ```txt 4 1 1 2 3 100 ``` >输出 ```txt 4 ```