A9978. Duff in Beach

While Duff was resting in the beach, she accidentally found a strange array $b_{0},b_{1},...,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_{0},...,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_{1}<i_{2}<...<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^{9}+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^{6}$ and $1<=l<=10^{18}$ ).

The second line contains $n$ space separated integers, $a_{0},a_{1},...,a_{n-1}$ ( $1<=a_{i}<=10^{9}$ for each $0<=i<=n-1$ ).

Print the answer modulo $1000000007$ in one line.

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