Description:
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 }$$.