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*_{*i*_{1}}, *b*_{*i*_{2}}, ..., *b*_{*i*_{*x*}}$ ($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*_{*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^{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.

Input

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

Output

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

Note

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