Duff in Beach

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.

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

• 1 ≤ x ≤ k
• For each 1 ≤ j ≤ x - 1,
• For each 1 ≤ j ≤ x - 1, b_ij ≤ b_ij + 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.

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).

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

3 5 3
5 9 1

10

5 10 3
1 2 3 4 5

25

 Note

In the first sample case, . So all such sequences are: , , , , , , , ,  and .