zyb bought n matryoshka dolls during his visit to Moscow, with sizes a1,a2,…,an, respectively, sorting from smallest to largest.
A matryoshka of size ii can be put into another matryoshka of size j if and only if j−i≥r, where rr is some given integer parameter.
zyb wishes to divide all n matryoshka dolls into kk groups, such that one can form a nestedmatryoshka doll in each group, where a group of matryoshka dolls with indices c1,c2,...,cm(1≤c1<c2<...<cm≤n) can form a nested matryoshka doll ∀1≤i<m,aci+r≤aci+1.
zyb wants to know how many ways there are to divide the n dolls into k groups satisfying the requirement above. Note that divisions such as1,2,3,4 and 3,4,1,2 are considered the same way. As the answer may be too large, you only need to output the answer modulo 998244353
The first line contains an integer T(1≤T≤20), denoting the number of test cases.
For each test case, the first line contains three integers n,k,r(1≤k≤n≤5000,1≤r≤109), denoting the number of matryoshka dolls, the number of groups zyb wants to divide into, and the parameter, respectively.
The next line contains n integers a1,a2,…,an(1≤a1≤a2≤...≤an≤109), denoting the sizes of the matryoshka dolls.
It is guaranteed that ∑n≤50000 over all test cases.
2
4 3 2
1 2 3 4
4 2 1
1 1 2 23
2