While Duff was resting in the beach, she accidentally found a strange array *b*<sub class="lower-index">0</sub>, *b*<sub class="lower-index">1</sub>, ..., *b*<sub class="lower-index">*l* - 1</sub> consisting of *l* positive integers. This array was strange because it was extremely long, but there was another (maybe shorter) array, *a*<sub class="lower-index">0</sub>, ..., *a*<sub class="lower-index">*n* - 1</sub> that *b* can be build from *a* with formula: *b*<sub class="lower-index">*i*</sub> = *a*<sub class="lower-index">*i* *mod* *n*</sub> 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*<sub class="lower-index">*i*<sub class="lower-index">1</sub></sub>, *b*<sub class="lower-index">*i*<sub class="lower-index">2</sub></sub>, ..., *b*<sub class="lower-index">*i*<sub class="lower-index">*x*</sub></sub> (0 ≤ *i*<sub class="lower-index">1</sub> &lt; *i*<sub class="lower-index">2</sub> &lt; ... &lt; *i*<sub class="lower-index">*x*</sub> &lt; *l*), such that: 
 -  1 ≤ *x* ≤ *k* -  For each 1 ≤ *j* ≤ *x* - 1, <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/8049e70898b1d8579ee1e94f4c68483c301ddfc5.png" style="max-width: 100.0%;max-height: 100.0%;"/> -  For each 1 ≤ *j* ≤ *x* - 1, *b*<sub class="lower-index">*i*<sub class="lower-index">*j*</sub></sub> ≤ *b*<sub class="lower-index">*i*<sub class="lower-index">*j* + 1</sub></sub>. i.e this subsequence is non-decreasing. 
Since this number can be very large, she want to know it modulo 10<sup class="upper-index">9</sup> + 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<sup class="upper-index">6</sup> and 1 ≤ *l* ≤ 10<sup class="upper-index">18</sup>).

The second line contains *n* space separated integers, *a*<sub class="lower-index">0</sub>, *a*<sub class="lower-index">1</sub>, ..., *a*<sub class="lower-index">*n* - 1</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup> for each 0 ≤ *i* ≤ *n* - 1).
n, l, k = list(map(int, input().split()))
a = list(map(int, input().split()))
if l < n:
    a = a[:l]
    n = len(a)
b = [0] * n
t = list(zip(a, range(n)))
t.sort()
rank = 0
for i in range(n):
    if i > 0 and t[i][0] != t[i - 1][0]:
        rank += 1
    b[t[i][1]] = rank
rank += 1

g = l // n
r = l % n
k = min(k, g + int(r > 0))
mod = 10 ** 9 + 7
# print('b=',b)
# print('n, l, k =', n,l,k, ',  g, r =', g, r)

bit = [0] * rank
def add(i, d):
    while 0 <= i < len(bit):
        bit[i] = (bit[i] + d) % mod
        i |= i + 1
def psum(i):
    ret = 0
    while 0 <= i < len(bit):
        ret = (ret + bit[i]) % mod
        i = (i & i + 1) - 1
    return ret

ret = 0
for kk in range(k):
    tmp = [0] * n
    for i in range(n):
        if kk == 0:
            last = 1
        else:
            last = psum(b[i])
        now = last
        rep = (g + int(i < r) - kk)
        # print(kk, 'i=', i, ' b[i]=', b[i], ' now=', now, 'rep=', rep)
        ret = (ret + now * rep % mod) % mod
        tmp[i] = now
    for i in range(n):
        add(b[i], tmp[i])
print(ret)