587B · Duff in Beach

Problem: While Duff was resting in the beach, she accidentally found a strange array b0, b1, ..., bl - 1 consisting of l positive integers. This array was strange because it was extremely long, but there was another (maybe shorter) array, a0, ..., an - 1 that b can be build from a with formula: bi = ai 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 bi1, bi2, ..., bix (0 ≤ i1 < i2 < ... < ix < l), such that:

• 1 ≤ x ≤ k
• For each 1 ≤ j ≤ x - 1, $\left\lfloor \frac { i j } { n } \right\rfloor + 1 = \left\lfloor \frac { i j + 1 } { n } \right\rfloor$
• For each 1 ≤ j ≤ x - 1, bij ≤ bij + 1. i.e this subsequence is non-decreasing.

Since this number can be very large, she want to know it modulo 109 + 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 Format: The first line of input contains three integers, n, l and k (1 ≤ n, k, n × k ≤ 106 and 1 ≤ l ≤ 1018).

The second line contains n space separated integers, a0, a1, ..., an - 1 (1 ≤ ai ≤ 109 for each 0 ≤ i ≤ n - 1).

Output Format: Print the answer modulo 1 000 000 007 in one line.

Note: In the first sample case, $b = \langle 5, 9, 1, 5, 9 \rangle$. So all such sequences are: $\langle b_{0}\rangle=\langle5\rangle$, $\langle b_{1}\rangle=\langle9\rangle$, $\langle b_{2}\rangle=\langle1\rangle$, $\langle b_{3}\rangle=\langle5\rangle$, $\langle b_{4}\rangle=\langle9\rangle$, ${ \langle b _ { 0 }, b _ { 3 } \rangle = \langle 5, 5 \rangle }$, ${ \langle b _ { 0 }, b _ { 4 } \rangle = \langle 5, 9 \rangle }$, ${ \langle b _ { 1 }, b _ { 4 } \rangle = \langle 9, 9 \rangle }$, ${ \langle b _ { 2 }, b _ { 3 } \rangle = \langle 1, 5 \rangle }$ and ${ \langle b _ { 2 }, b _ { 4 } \rangle = \langle 1, 9 \rangle }$.