Problem1797--2020DLOI初中 第五题 好子集

1797: 2020DLOI初中 第五题 好子集

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MB

Description

      给出一个包含n个元素的数组a[1...n]。从数组选中m个数,不妨假设是a[i1],a[i2],a[i3],...a[im], 其中i1 < i2 < i3 <...<im,选中的这m个数就构成a数组的一个“子集”,如果该“子集”的最大值与该“子集”的最小值的差不超过k,那么该“子集”就是“好子集”。

      你的任务是计算有多少个不同的“好子集”,答案模1000000007

Input

第一行,3个正整数n,m,k1<=n<=2000001<=m<=100, 1<=k<=n

第二行,n个整数,第i个整数是a[i]1<=a[i]<=na数组的元素可能有重复的数。

Output

一个整数。

Sample Input Copy

4 3 2
1 2 4 3

Sample Output Copy

2

Source/Category