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.

<image>

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, <image>
  * 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

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

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

Examples

Input

3 5 3
5 9 1


Output

10


Input

5 10 3
1 2 3 4 5


Output

25

Note

In the first sample case, <image>. So all such sequences are: <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image>, <image> and <image>.
#include <bits/stdc++.h>
using namespace std;
long long M = 1e9 + 7;
const long long INF = LLONG_MAX;
void comps(long long st, vector<set<long long> > *edges, long long *visited,
           long long *cats, long long *cnt, long long curr_cnt,
           long long max_cnt, long long m) {
  visited[st] = 1;
  set<long long>::iterator it;
  set<long long> x1 = (*edges)[st];
  if (cats[st] == 1) {
    curr_cnt = curr_cnt + 1;
  } else {
    curr_cnt = 0;
  }
  max_cnt = max(max_cnt, curr_cnt);
  long long lf = 0;
  for (it = x1.begin(); it != x1.end(); ++it) {
    if (visited[(*it)] == -1) {
      ++lf;
      comps((*it), edges, visited, cats, cnt, curr_cnt, max_cnt, m);
    }
  }
  if (lf == 0) {
    if ((max_cnt) <= m) {
      (*cnt) = (*cnt) + 1;
    }
  }
}
long long power_2(long long p1, long long p2) {
  if (p2 == 0) {
    return 1;
  }
  if (p2 == 1) {
    return p1 % M;
  }
  long long y = power_2(p1, p2 / 2);
  y = ((((y * y) % M) * power_2(p1, p2 % 2)) % M);
  return y;
}
long long inv(long long p1) { return power_2(p1, M - 2); }
long long fact(long long n) {
  long long i, nlt = 1;
  for (i = 1; i <= n; ++i) {
    nlt = (nlt * i) % M;
  }
  return nlt;
}
long long popcount1(long long i) {
  long long cnt = 0;
  while (i > 0) {
    if (i % 2 == 1) {
      ++cnt;
    }
    i = i / 2;
  }
  return cnt;
}
long long lf_cnt = 0;
void recurse(long long st, vector<set<pair<long long, long long> > > *edges,
             long long *arr, long long n, int *dp) {
  arr[st] = 1;
  long long i, j;
  fill(dp, dp + 2 * n + 2, 0);
  set<pair<long long, long long> >::iterator it;
  set<pair<long long, long long> > x1 = (*edges)[st];
  long long lf = 0;
  int *bp = new int[2 * n + 2];
  int *cp = new int[2 * n + 2];
  for (it = x1.begin(); it != x1.end(); ++it) {
    if (arr[(*it).first] == -1) {
      recurse((*it).first, edges, arr, n, bp);
      ++lf;
      if (lf == 1) {
        for (i = 0; i <= n; ++i) {
          dp[i] = min(bp[i], bp[n + 1 + i] + 1);
        }
        for (i = i; i <= 2 * n + 1; ++i) {
          dp[i] = min(bp[i - n - 1] + 1, bp[i]);
        }
      } else {
        for (i = 0; i <= n; ++i) {
          cp[i] = dp[0] + min(bp[i], bp[n + i + 1] + 1);
          for (j = 0; j <= i; ++j) {
            cp[i] = dp[j] + min(bp[i - j], bp[n + (i - j) + 1] + 1);
          }
        }
        for (i = i; i <= 2 * n + 1; ++i) {
          cp[i] = dp[i] + min(bp[0] + 1, bp[n + 1]);
          for (j = 0; j <= i - n - 1; ++j) {
            cp[i] = dp[j] + min(bp[i - j - n - 1] + 1, bp[i - j]);
          }
        }
        for (i = 0; i <= 2 * n + 1; ++i) {
          dp[i] = cp[i];
        }
      }
    }
    delete (cp);
    delete (bp);
  }
  if (lf == 0) {
    dp[0] = 0;
    dp[1] = 0;
    ++lf_cnt;
  }
}
void eql(long long **a, long long **b, long long n) {
  long long i, j;
  for (i = 1; i <= n; ++i) {
    for (j = 1; j <= n; ++j) {
      a[i - 1][j - 1] = b[i - 1][j - 1];
    }
  }
}
bool cheql(long long **a, long long **b, long long n) {
  bool ans = true;
  long long i, j;
  for (i = 1; i <= n; ++i) {
    for (j = 1; j <= n; ++j) {
      ans = ans & (a[i - 1][j - 1] == b[i - 1][j - 1]);
      if (!(a[i - 1][j - 1] == b[i - 1][j - 1])) {
      }
    }
  }
  return ans;
}
void init1(long long ***a, long long n) {
  *a = new long long *[n];
  long long i;
  for (i = 1; i <= n; ++i) {
    (*a)[i - 1] = new long long[n];
    fill((*a)[i - 1], (*a)[i - 1] + n, 0);
  }
}
long long gcd(long long a, long long b) {
  if (a > b) {
    return gcd(b, a);
  }
  if (a == b || a == 0) {
    return b;
  }
  return gcd(b % a, a);
}
void calc_failure(string t, vector<long long> *fail) {
  long long i, j, k;
  (*fail).push_back(0);
  (*fail).push_back(0);
  for (i = 2; i <= t.length(); ++i) {
    long long curr = i - 1;
    while (true) {
      if (t[(*fail)[curr]] == t[i - 1]) {
        (*fail).push_back(((*fail)[curr]) + 1);
        break;
      } else {
        if (curr == 0) {
          (*fail).push_back(0);
          break;
        }
        curr = (*fail)[curr];
      }
    }
  }
}
void patt(string s, string t, vector<long long> *start,
          vector<long long> *end) {
  long long i, j, k;
  i = 0;
  j = 0;
  long long n, m;
  n = t.length();
  m = s.length();
  vector<long long> fail;
  calc_failure(t, &fail);
  while (i < m) {
    bool ans = true;
    while (j < n && i < m) {
      if (s[i] == t[j]) {
        ++i;
        ++j;
      } else {
        ans = false;
        break;
      }
    }
    if (j == n) {
      (*start).push_back(i - n);
      (*end).push_back(i - 1);
    }
    if (j == 0) {
      ++i;
    }
    j = fail[j];
  }
}
bool check_pr(long long x, vector<long long> *pr) {
  long long n = (*pr).size();
  long long i;
  for (i = 0; i < n && ((*pr)[i]) * ((*pr)[i]) <= x; ++i) {
    if (x % ((*pr)[i]) == 0) {
      return false;
    }
  }
  return true;
}
int main() {
  vector<pair<long long, long long> > xx;
  long long n, m, d, p, l, r, t1, q, x, y, z, a, b, c, sum = 0, mult = 1, t = 0;
  long long i, j, k;
  string s, s1;
  t1 = 1;
  while (t1-- > 0) {
    cin >> n >> l >> k;
    long long *arr = new long long[n];
    long long *brr = new long long[n];
    for (i = 1; i <= n; ++i) {
      scanf("%I64d", &arr[i - 1]);
      brr[i - 1] = arr[i - 1];
    }
    sort(arr, arr + n);
    long long **dp = new long long *[k];
    for (i = 1; i <= k; ++i) {
      dp[i - 1] = new long long[n];
      fill(dp[i - 1], dp[i - 1] + n, 0);
    }
    dp[0][0] = 1;
    vector<long long> src;
    for (i = 1; i <= n; ++i) {
      long long ind = upper_bound(arr, arr + n, arr[i - 1]) - arr;
      src.push_back(--ind);
    }
    for (i = 2; i <= n; ++i) {
      dp[0][i - 1] = dp[0][i - 2] + 1;
    }
    for (j = 2; j <= k; ++j) {
      sum = 0;
      for (i = 1; i <= n; ++i) {
        dp[j - 1][i - 1] = dp[j - 2][src[i - 1]];
        sum = (sum + dp[j - 1][i - 1]) % M;
        dp[j - 1][i - 1] = sum;
      }
    }
    long long ans = 0;
    for (i = 1; i <= k; ++i) {
      if (i * n > l) {
        break;
      }
      long long val2 = l / n;
      val2 = val2 - i + 1;
      val2 = val2 % M;
      ans = (ans + ((dp[i - 1][n - 1] * val2) % M)) % M;
    }
    if (l % n == 0) {
      cout << ans;
      continue;
    }
    for (i = 1; i <= l % n; ++i) {
      long long ind = upper_bound(arr, arr + n, brr[i - 1]) - arr;
      --ind;
      for (j = 1; j <= k; ++j) {
        if ((j - 1) * n > (l - (l % n))) {
          break;
        }
        if (j >= 2) {
          ans = (ans + dp[j - 2][ind]) % M;
        } else {
          ans = (ans + 1) % M;
        }
      }
    }
    cout << ans;
  }
  return 0;
}
