Duff in Beach

2000ms

262144K

Description:

While Duff was resting in the beach, she accidentally found a strange array b₀, b₁, ..., b_l - 1 consisting of l positive integers. This array was strange because it was extremely long, but there was another (maybe shorter) array, a₀, ..., a_n - 1 that b can be build from a with formula: b_i = a_{i mod n} where a mod b denoted the remainder of dividing a by b.

$\text{[math]}$

Duff is so curious, she wants to know the number of subsequences of b like b_i₁, b_i₂, ..., b_{i_x} (0 ≤ i₁ < i₂ < ... < i_x < l), such that:

1 ≤ x ≤ k
For each 1 ≤ j ≤ x - 1, $\text{[math]}$
For each 1 ≤ j ≤ x - 1, b_{i_j} ≤ b_{i_j + 1}. i.e this subsequence is non-decreasing.

Since this number can be very large, she want to know it modulo 10⁹ + 7.

Duff is not a programmer, and Malek is unavailable at the moment. So she asked for your help. Please tell her this number.

Input:

The first line of input contains three integers, n, l and k (1 ≤ n, k, n × k ≤ 10⁶ and 1 ≤ l ≤ 10¹⁸).

The second line contains n space separated integers, a₀, a₁, ..., a_n - 1 (1 ≤ a_i ≤ 10⁹ for each 0 ≤ i ≤ n - 1).

Output:

Print the answer modulo 1 000 000 007 in one line.

Sample Input:

3 5 3
5 9 1

Sample Output:

Sample Input:

5 10 3
1 2 3 4 5

Sample Output:

Note:

In the first sample case, $\text{[math]}$ . So all such sequences are: $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ and $\text{[math]}$ .

Informação

Provedor Codeforces

Código CF587B