Description

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.

Input Format

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 Format

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

4 1
1 2 3 100

4

6 9
10 20 20 10 10 20

36

Hint

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 day 2 T3 tower.

The translation copyright belongs to the problem provider

Translated by ChatGPT 5