#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:500000000")
using namespace std;
const int mod = 1000000007;
template <typename Type, class MainOperator, class AddOperator = MainOperator>
class SegmentTree {
 protected:
  vector<Type> t;
  int ppow;
  Type defaultValue;
  MainOperator Operator;
  AddOperator addOperator;
  void _construct(int size, Type defaultValue, Type value) {
    ppow = size;
    while (ppow & (ppow - 1)) ppow++;
    this->defaultValue = defaultValue;
    t.resize(ppow * 2);
    for (int i = 0; i < ppow; i++)
      t[i + ppow] = i < size ? value : defaultValue;
    for (int i = ppow - 1; i > 0; i--) t[i] = Operator(t[i * 2], t[i * 2 + 1]);
  }

 public:
  SegmentTree(int size, Type defaultValue) {
    _construct(size, defaultValue, defaultValue);
  }
  SegmentTree(int size, Type defaultValue, Type value) {
    _construct(size, defaultValue, value);
  }
  template <typename Iterator>
  SegmentTree(Iterator begin, Iterator end, Type defaultValue) {
    this->defaultValue = defaultValue;
    vector<Type> values(begin, end);
    ppow = values.size();
    while (ppow & (ppow - 1)) ppow++;
    t.assign(ppow * 2, defaultValue);
    for (int i = 0; i < (int)values.size(); i++) t[i + ppow] = values[i];
    for (int i = ppow - 1; i > 0; i--) t[i] = Operator(t[i * 2], t[i * 2 + 1]);
  }
  Type Get(int L, int R) {
    L += ppow;
    R += ppow;
    Type res = defaultValue;
    while (L <= R) {
      if (L & 1) res = Operator(res, t[L++]);
      if (~R & 1) res = Operator(res, t[R--]);
      L /= 2;
      R /= 2;
    }
    return res;
  }
  void Add(int pos, Type value) {
    pos += ppow;
    t[pos] = addOperator(t[pos], value);
    pos /= 2;
    while (pos > 0) {
      t[pos] = Operator(t[pos * 2], t[pos * 2 + 1]);
      pos /= 2;
    }
  }
};
template <typename Type>
struct Sum {
  Type operator()(Type a, Type b) { return (a + b) % mod; }
};
int dp[1000009];
int main() {
  long long L;
  int n, K, i, j;
  scanf("%d %I64d %d", &n, &L, &K);
  vector<int> a(n);
  map<int, int> NX;
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    NX[a[i]] = 0;
  }
  int cnt = 0;
  for (auto &p : NX) p.second = cnt++;
  auto tree = SegmentTree<int, Sum<int> >(cnt, 0);
  tree.Add(0, 1);
  for (auto &v : a) v = NX[v];
  int res = 0;
  for (int len = 1; len <= K; len++) {
    auto ntree = SegmentTree<int, Sum<int> >(cnt, 0);
    for (i = 0; i < n; i++) {
      auto x = a[i];
      dp[i] = tree.Get(0, x);
      ntree.Add(x, dp[i]);
      res = (res + max(0LL, L / n - len + 1 + (i < L % n)) % mod * dp[i]) % mod;
    }
    tree = ntree;
  }
  cout << res << endl;
}

### Prompt

In CPP, your task is to solve the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:500000000")
using namespace std;
const int mod = 1000000007;
template <typename Type, class MainOperator, class AddOperator = MainOperator>
class SegmentTree {
 protected:
  vector<Type> t;
  int ppow;
  Type defaultValue;
  MainOperator Operator;
  AddOperator addOperator;
  void _construct(int size, Type defaultValue, Type value) {
    ppow = size;
    while (ppow & (ppow - 1)) ppow++;
    this->defaultValue = defaultValue;
    t.resize(ppow * 2);
    for (int i = 0; i < ppow; i++)
      t[i + ppow] = i < size ? value : defaultValue;
    for (int i = ppow - 1; i > 0; i--) t[i] = Operator(t[i * 2], t[i * 2 + 1]);
  }

 public:
  SegmentTree(int size, Type defaultValue) {
    _construct(size, defaultValue, defaultValue);
  }
  SegmentTree(int size, Type defaultValue, Type value) {
    _construct(size, defaultValue, value);
  }
  template <typename Iterator>
  SegmentTree(Iterator begin, Iterator end, Type defaultValue) {
    this->defaultValue = defaultValue;
    vector<Type> values(begin, end);
    ppow = values.size();
    while (ppow & (ppow - 1)) ppow++;
    t.assign(ppow * 2, defaultValue);
    for (int i = 0; i < (int)values.size(); i++) t[i + ppow] = values[i];
    for (int i = ppow - 1; i > 0; i--) t[i] = Operator(t[i * 2], t[i * 2 + 1]);
  }
  Type Get(int L, int R) {
    L += ppow;
    R += ppow;
    Type res = defaultValue;
    while (L <= R) {
      if (L & 1) res = Operator(res, t[L++]);
      if (~R & 1) res = Operator(res, t[R--]);
      L /= 2;
      R /= 2;
    }
    return res;
  }
  void Add(int pos, Type value) {
    pos += ppow;
    t[pos] = addOperator(t[pos], value);
    pos /= 2;
    while (pos > 0) {
      t[pos] = Operator(t[pos * 2], t[pos * 2 + 1]);
      pos /= 2;
    }
  }
};
template <typename Type>
struct Sum {
  Type operator()(Type a, Type b) { return (a + b) % mod; }
};
int dp[1000009];
int main() {
  long long L;
  int n, K, i, j;
  scanf("%d %I64d %d", &n, &L, &K);
  vector<int> a(n);
  map<int, int> NX;
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    NX[a[i]] = 0;
  }
  int cnt = 0;
  for (auto &p : NX) p.second = cnt++;
  auto tree = SegmentTree<int, Sum<int> >(cnt, 0);
  tree.Add(0, 1);
  for (auto &v : a) v = NX[v];
  int res = 0;
  for (int len = 1; len <= K; len++) {
    auto ntree = SegmentTree<int, Sum<int> >(cnt, 0);
    for (i = 0; i < n; i++) {
      auto x = a[i];
      dp[i] = tree.Get(0, x);
      ntree.Add(x, dp[i]);
      res = (res + max(0LL, L / n - len + 1 + (i < L % n)) % mod * dp[i]) % mod;
    }
    tree = ntree;
  }
  cout << res << endl;
}

```