题目背景

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

题目描述

这座塔共有 $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$ 的结果。

4 1
1 2 3 100

4

6 9
10 20 20 10 10 20

36

提示

【样例解释】

样例 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 day 2 T3 tower。

翻译版权为题目提供者