Bob is playing with an array of ~N~ integers named ~a~. Bob calls a subarray of ~a~ good if the maximum frequency of a number does not exceed ~F~. Bob also calls a subarray great if the sum of the numbers in the subarray does not exceed ~S~. Finally, Bob calls an array great-good if it is both a good array and a great array. Bob wants you to find the number of great subarrays multiplied by the number of good subarrays multiplied by the number of great-good subarrays. Since this number can be quite large, output it modulo ~10^9+7~.

Note: An empty subarray is not acceptable.

Constraints

~1 \le N \le 10^5~
~1 \le a_i \le 10^5~ for all ~1 \le i \le N~
~1 \le F \le N~
~1 \le S \le 10^{12}~

Subtask 1 [10%]

~1 \le N \le 50~

Subtask 2 [20%]

~1 \le N \le 10^3~

Subtask 3 [70%]

No additional constraints.

Input Specification

The first line of input will contain 3 integers ~N~, ~F~, and ~S~, all separated by a single space.
The next line of input will contain ~N~ integers each separated by a space, which is the array ~a~.

Output Specification

Output 1 integer, the number of great subarrays multiplied by the number of good subarrays multiplied by the number of great-good subarrays modulo ~10^9+7~.

Sample Input 1

3 2 4
1 2 3

Sample Output 1

96

Sample Input 2

10 3 10
2 3 5 2 2 3 4 1 4 1

Sample Output 2

46255