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