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;
const int max_n = 1111111, inf = 1000000007;
int n, k, a[max_n], t[max_n];
pair<int, int> b[max_n];
long long l;
vector<vector<int> > dp;
void proc() {
  sort(b, b + n);
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    while (i + 1 < n && b[i].first == b[i + 1].first) {
      a[b[i].second] = cnt;
      ++i;
    }
    a[b[i].second] = cnt;
    ++cnt;
  }
}
void update(int i, int x) {
  for (; i <= n; i = (i | (i + 1))) {
    t[i] += x;
    t[i] %= inf;
    if (t[i] < 0) {
      t[i] += inf;
    }
  }
}
int get(int r) {
  int res = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) {
    res += t[r];
    res %= inf;
  }
  return res;
}
int main() {
  cin >> n >> l >> k;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    b[i] = make_pair(a[i], i);
  }
  proc();
  dp.resize(k);
  for (int i = 0; i < k; ++i) {
    dp[i].resize(n);
  }
  for (int i = 0; i < n; ++i) {
    dp[0][i] = 1;
    update(a[i], 1);
  }
  for (int i = 1; i < k; ++i) {
    for (int j = 0; j < n; ++j) {
      dp[i][j] = get(a[j]);
    }
    for (int j = 0; j < n; ++j) {
      int x = dp[i][j] - dp[i - 1][j];
      x %= inf;
      if (x < 0) {
        x += inf;
      }
      update(a[j], x);
    }
  }
  long long all = l / n;
  int ans = 0, to = l % n;
  for (int cnt = 0; cnt < k; ++cnt) {
    if (cnt + 1 <= all) {
      int C = (all - cnt) % inf;
      for (int i = 0; i < n; ++i) {
        int pl = (1LL * dp[cnt][i] * C) % inf;
        ans += pl;
        ans %= inf;
      }
    }
    if (cnt <= all) {
      int C = 1;
      for (int i = 0; i < to; ++i) {
        int pl = (1LL * dp[cnt][i] * C) % inf;
        ans += pl;
        ans %= inf;
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}
