该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

阿尔法星区的星际防御指挥部接到紧急任务：需在边境空间站部署 $\rm N$ 台脉冲能量发生器 , 构建区域性防御屏障

每台发生器的能量频率参数记录为 $\rm F_1, F_2, \cdots, F_N$ , 该参数决定了发生器的防御覆盖范围

更关键的是 , 频率参数过于接近的发生器若接入同一能量回路会引发频率共振 , 导致回路过载瘫痪

为确保防御系统稳定运行 , 指挥官需将这 $\rm N$ 台发生器分配到 $\rm M$ 条独立的能量回路中 , 且必须遵守核心部署准则：同一条能量回路内 , 任意两台发生器的频率参数差距 至少为 $\rm D$

作为防御系统的首席工程师请你计算：有多少种不同的回路部署方案能满足安全准则？

每个能量回路都相同 , 即方案 $\set{1,4},\set{2,3}$ 与方案 $\set{2,3},\set{1,4}$ 视为相同

输入格式

第一行输入三个空格分隔的整数 $\rm N, M, D$

第二行输入 $\rm N$ 个空格分隔的整数 $\rm F_1, F_2, \cdots, F_N$

输出格式

输出一个整数 , 表示满足安全准则的不同部署方案的总数

答案可能很大 $\rm mod ~ 1000000007$ 后输出

4 3 2
1 2 3 4

3

样例1解释

三种部署方案分别为 $\big\{\set{1,4},\set{2},\set{3}\big\}$、$\big\{\set{1,3},\set{2},\set{4}\big\}$、$\big\{\set{2,4},\set{1},\set{3}\big\}$

4 2 1
1 1 2 2

2

样例2解释

发生器使用不同颜色区分 $\rm \textcolor{red}{1} , \textcolor{green}{1}, \textcolor{blue}{2} , \textcolor{orange}{2}$

两种分组方式分别为 $\big\{\set{\textcolor{red}{1},\textcolor{blue}{2}},\set{\textcolor{green}{1},\textcolor{orange}{2}}\big\}$、$\big\{\set{\textcolor{red}{1},\textcolor{orange}{2}},\set{\textcolor{green}{1},\textcolor{blue}{2}}\big\}$

大样例

数据规模

测试点 $1 \sim 2$ 满足 $\rm N \leq 12$

测试点 $3 \sim 4$ 满足 $\rm D=0$

测试点 $5 \sim 7$ 满足 $\rm D=1$

测试点 $8 \sim 14$ 满足 $\rm M = 2$

测试点 $15 \sim 18$ 满足 $\rm 1 \leq N \leq 450$

测试点 $19 \sim 25$ 满足 $\rm 1 \leq M \leq N \leq 5000 , 0 \leq D \leq 10^9 , 1 \leq F_i \leq 10^9$