튜토리얼 그룹 나누기

UCF에는 COT 3100(Introduction to Discrete Mathematics)처럼 매우 큰 강의가 있습니다. 이런 대형 강의에서는 잘 배우지 못하는 학생도 있습니다. UCF에는 아는 것이 많은 학생도 많은데, 이 문제에서는 이들을 TA라고 부릅니다. 수업을 TA가 이끄는 작은 튜토리얼 그룹으로 나누면 학생들이 자신의 잠재력을 더 잘 발휘할 수 있습니다.

튜토리얼 그룹이 잘 운영되려면 그룹에 속한 학생들의 지식 수준이 서로 가까워야 합니다. 그룹 내 지식 수준의 최솟값과 최댓값의 차이는 주어진 값 k를 넘을 수 없습니다. 그룹의 학생 수는 s명을 넘을 수 없으며, 각 그룹에는 최소 한 명의 학생이 있어야 합니다. 그룹들은 T1, T2, ..., Tm 순으로 나열할 수 있어야 하며, 모든 정수 i(1 ≤ i < m)에 대해 Ti의 최대 지식 수준이 Ti+1의 최소 지식 수준보다 엄격히 낮아야 합니다. TA는 충분히 많으므로 튜토리얼 그룹의 개수는 제한이 없습니다.

예를 들어 지식 수준이 10, 6, 5, 9, 12이고 k = 5, s = 3이라고 하겠습니다. 이 수업은 다음 13가지 방법으로 튜토리얼 그룹에 나눌 수 있습니다.

1. {5}, {6}, {9}, {10}, {12}
2. {5}, {6}, {9}, {10, 12}
3. {5}, {6}, {9, 10}, {12}
4. {5}, {6}, {9, 10, 12}
5. {5}, {6, 9}, {10}, {12}
6. {5}, {6, 9}, {10, 12}
7. {5}, {6, 9, 10}, {12}
8. {5, 6}, {9}, {10}, {12}
9. {5, 6}, {9}, {10, 12}
10. {5, 6}, {9, 10}, {12}
11. {5, 6}, {9, 10, 12}
12. {5, 6, 9}, {10}, {12}
13. {5, 6, 9}, {10, 12}

각 학생의 지식 수준, 최대 차이 k, 최대 그룹 크기 s가 주어졌을 때, COT 3100 강의를 맡은 Travis Meade 교수는 튜토리얼 그룹을 만드는 방법이 몇 가지인지 알고 싶어 합니다. 답은 $10^9 + 7$로 나눈 나머지로 구하세요.

첫 줄에 공백으로 구분된 정수 세 개 n(1 ≤ n ≤ 10,000), k(1 ≤ k ≤ $10^9$), s(1 ≤ s ≤ 100)가 주어집니다. n은 학생 수이고, k는 한 튜토리얼 그룹 안에서 허용되는 지식 수준의 최대 차이이며, s는 한 튜토리얼 그룹의 최대 학생 수입니다.

둘째 줄에는 공백으로 구분된 정수 n개가 주어집니다. i번째 정수 a_i(1 ≤ a_i ≤ $10^9$)는 i번째 학생의 지식 수준입니다. 모든 지식 수준은 서로 다릅니다.

튜토리얼 그룹을 만드는 방법의 수를 $10^9 + 7$로 나눈 나머지를 출력합니다. 어떤 그룹(집합)이 한 방법에는 들어 있고 다른 방법에는 없으면, 두 방법은 서로 다른 것으로 봅니다.