古巴比伦人决定建造一座巨塔。这座塔由 $N$ 个立方体积木叠放而成。巴比伦人从全国各地收集了许多不同大小的积木。从上一次失败的尝试中，他们吸取了教训：如果将一个大积木直接放在一个比它小得多的积木上，塔就会倒塌。
即使大小相同，任意两个积木也是不同的（即它们是可区分的）。对于每个积木，都会给出它的边长。同时还会给出一个整数 $D$，其含义如下：如果积木 $A$ 的边长严格大于积木 $B$ 的边长加上 $D$，则不允许将积木 $A$ 直接放在积木 $B$ 的上方。
计算使用所有积木建造该塔的不同方案数。由于这个数量可能非常大，请输出结果模 $10^9 + 9$ 的余数。
输入格式
输入的第一行包含两个正整数 $N$ 和 $D$，分别表示积木的数量和容差。
第二行包含 $N$ 个空格分隔的整数，每个整数表示一个积木的边长。
输出格式
输出单行，包含一个整数：可以建造的塔的数量模 $1\,000\,000\,009$ 的余数。
数据范围
- 输入中的所有数字均为不超过 $10^9$ 的正整数。
- $N$ 至少为 $2$。
- 在占 $70$ 分的测试点中，$N \le 70$。
- 其中，在占 $45$ 分的测试点中，$N \le 20$。
- 其中，在占 $10$ 分的测试点中，$N \le 10$。
- 对于某些测试点，合法塔的总数不会超过 $1\,000\,000$。这些测试点总共占 $30$ 分。
- 对于最后六个测试点（占 $30$ 分），$N > 70$。这些测试点没有给出 $N$ 的上限。
样例
输入样例 1
4 1 1 2 3 100
输出样例 1
4
说明 1
我们可以将前三个积木以任意顺序排列，除了（自底向上）2,1,3 或 1,3,2。最后一个积木（边长为 100）必须放在最底部。
输入样例 2
6 9 10 20 20 10 10 20
输出样例 2
36
说明 2
我们不能将边长为 20 的积木直接放在边长为 10 的积木上。排列边长为 10 的积木有 6 种方式，排列边长为 20 的积木也有 6 种方式。