题目描述

给定一个长度为 $n$ 的序列 $a$。请计算有多少个由 $m$ 个下标组成的元组 $(i_1,i_2,\ldots,i_m)$ 满足：

• $1\le i_1<i_2<\cdots<i_m\le n$；
• 在选出的 $m$ 个数中，最大值与最小值之差不超过 $k$。

答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $t$，表示测试组数。

每组数据第一行三个整数 $n,m,k$，分别表示序列长度、需要选择的元素个数以及允许的最大差值。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每组数据输出一行一个整数，表示答案对 $10^9+7$ 取模后的结果。

样例

4
4 3 2
1 2 4 3
4 2 1
1 1 1 1
1 1 1
1
10 4 3
5 6 1 3 2 9 8 1 2 4

2
6
1
20

数据范围

$1\le t\le2\times10^5$，$1\le n\le2\times10^5$，$1\le m\le100$，$1\le k\le n$，$1\le a_i\le n$。

所有测试组的 $n$ 之和不超过 $2\times10^5$。