Problem: Shrimpy Duc is a fat and greedy boy who is always hungry. After a while of searching for food to satisfy his never-ending hunger, Shrimpy Duc finds M&M candies lying unguarded on a L × L grid. There are n M&M candies on the grid, the i-th M&M is currently located at (x_i + 0.5, y_i + 0.5), and has color c_i out of a total of k colors (the size of M&Ms are insignificant).

Shrimpy Duc wants to steal a rectangle of M&Ms, specifically, he wants to select a rectangle with integer coordinates within the grid and steal all candies within the rectangle. Shrimpy Duc doesn't need to steal every single candy, however, he would like to steal at least one candy for each color.

In other words, he wants to select a rectangle whose sides are parallel to the coordinate axes and whose left-bottom vertex (X_1, Y_1) and right-top vertex (X_2, Y_2) are points with integer coordinates satisfying 0 ≤ X_1 < X_2 ≤ L and 0 ≤ Y_1 < Y_2 ≤ L, so that for every color 1 ≤ c ≤ k there is at least one M&M with color c that lies within that rectangle.

How many such rectangles are there? This number may be large, so you only need to find it modulo 10^9 + 7.

Input

The first line contains three positive integers n, k, L (1 ≤ k ≤ n ≤ 2 ⋅ 10^3, 1 ≤ L ≤ 10^9 ) — the number of M&Ms, the number of colors and the length of the grid respectively.

The following n points describe the M&Ms. Each line contains three integers x_i, y_i, c_i (0 ≤ x_i, y_i < L, 1 ≤ c_i ≤ k) — the coordinates and color of the i-th M&M respectively. 

Different M&Ms have different coordinates (x_i ≠ x_j or y_i ≠ y_j for every i ≠ j), and for every 1 ≤ c ≤ k there is at least one M&M with color c.

Output

Output a single integer — the number of rectangles satisfying Shrimpy Duc's conditions, modulo 10^9 + 7.

Examples

Input


4 2 4
3 2 2
3 1 1
1 1 1
1 2 1


Output


20


Input


5 3 10
6 5 3
5 3 1
7 9 1
2 3 2
5 0 2


Output


300


Input


10 4 10
5 4 4
0 0 3
6 0 1
3 9 2
8 7 1
8 1 3
2 1 3
6 3 2
3 5 3
4 3 4


Output


226

Note

Grid for the first sample:

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 5;
const int MAXD = 2e3 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline void add_mod(int &a, int b) {
  if ((a += b) >= mod) a -= mod;
}
inline long long pw(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
template <typename T>
struct DSC {
  T dsc[MAXN];
  int dcnt;
  DSC(void) : dcnt(0) {}
  inline void clear(void) { dcnt = 0; }
  inline T operator[](const int x) { return dsc[x]; }
  inline const T &operator[](const int x) const { return dsc[x]; }
  inline int size(void) { return dcnt; }
  inline void insert(const T &x) { dsc[++dcnt] = x; }
  inline void build(void) {
    sort(dsc + 1, dsc + dcnt + 1);
    dcnt = unique(dsc + 1, dsc + dcnt + 1) - dsc - 1;
  }
  inline int get(const T &x) {
    return lower_bound(dsc + 1, dsc + dcnt + 1, x) - dsc;
  }
};
struct Segment_Tree {
  int st[MAXN << 2], nd[MAXN << 2], sum[MAXN << 2], s[MAXN << 2],
      tag[MAXN << 2];
  inline void push_up(int u) {
    if (st[((u) << 1)] == st[((u) << 1 | 1)]) {
      st[u] = st[((u) << 1)];
      nd[u] = min(nd[((u) << 1)], nd[((u) << 1 | 1)]);
      s[u] = (s[((u) << 1)] + s[((u) << 1 | 1)]) % mod;
    } else {
      if (st[((u) << 1)] < st[((u) << 1 | 1)])
        st[u] = st[((u) << 1)], nd[u] = min(nd[((u) << 1)], st[((u) << 1 | 1)]),
        s[u] = s[((u) << 1)];
      else
        st[u] = st[((u) << 1 | 1)],
        nd[u] = min(nd[((u) << 1 | 1)], st[((u) << 1)]),
        s[u] = s[((u) << 1 | 1)];
    }
    sum[u] = (sum[((u) << 1)] + sum[((u) << 1 | 1)]) % mod;
  }
  inline void push_down(int u) {
    if (tag[u]) {
      if (st[((u) << 1)] + tag[u] == st[u])
        st[((u) << 1)] += tag[u], tag[((u) << 1)] += tag[u],
            sum[((u) << 1)] =
                (sum[((u) << 1)] + (long long)tag[u] * s[((u) << 1)]) % mod;
      if (st[((u) << 1 | 1)] + tag[u] == st[u])
        st[((u) << 1 | 1)] += tag[u], tag[((u) << 1 | 1)] += tag[u],
            sum[((u) << 1 | 1)] =
                (sum[((u) << 1 | 1)] + (long long)tag[u] * s[((u) << 1 | 1)]) %
                mod;
      tag[u] = 0;
    }
  }
  void build(int u, int l, int r, int a[], int val[]) {
    tag[u] = 0;
    if (l == r) {
      st[u] = a[l];
      s[u] = val[l];
      nd[u] = inf;
      sum[u] = (long long)a[l] * val[l] % mod;
      return;
    }
    int mid = (l + r) >> 1;
    build(((u) << 1), l, mid, a, val);
    build(((u) << 1 | 1), mid + 1, r, a, val);
    push_up(u);
  }
  void update(int u, int l, int r, int ql, int qr, int k) {
    if (st[u] >= k) return;
    if (l == r) {
      st[u] = k;
      sum[u] = (long long)k * s[u] % mod;
      return;
    }
    if (ql <= l && r <= qr) {
      if (nd[u] <= k) {
        push_down(u);
        int mid = (l + r) >> 1;
        update(((u) << 1), l, mid, ql, qr, k);
        update(((u) << 1 | 1), mid + 1, r, ql, qr, k);
        push_up(u);
        return;
      }
      tag[u] += k - st[u];
      sum[u] = (sum[u] + (long long)(k - st[u]) * s[u]) % mod;
      st[u] = k;
      return;
    }
    push_down(u);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(((u) << 1), l, mid, ql, qr, k);
    if (mid < qr) update(((u) << 1 | 1), mid + 1, r, ql, qr, k);
    push_up(u);
  }
  int query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sum[u];
    push_down(u);
    int mid = (l + r) >> 1, res = 0;
    if (ql <= mid) add_mod(res, query(((u) << 1), l, mid, ql, qr));
    if (mid < qr) add_mod(res, query(((u) << 1 | 1), mid + 1, r, ql, qr));
    push_up(u);
    return res;
  }
};
struct Node {
  int x, y, clr;
} p[MAXN];
int main(void) {
  int n, d, L;
  scanf("%d%d%d", &n, &d, &L);
  for (int i = 1; i <= n; ++i)
    scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].clr), ++p[i].x, ++p[i].y;
  static DSC<int> dscx, dsc;
  for (int i = 1; i <= n; ++i) dscx.insert(p[i].x), dsc.insert(p[i].y);
  dscx.insert(L + 1);
  dsc.insert(L + 1);
  dscx.build();
  dsc.build();
  for (int i = 1; i <= n; ++i)
    p[i].x = dscx.get(p[i].x), p[i].y = dsc.get(p[i].y);
  static vector<Node> nodex[MAXN], nodey[MAXN];
  for (int i = 1; i <= n; ++i)
    nodex[p[i].x].push_back(p[i]), nodey[p[i].y].push_back(p[i]);
  long long ans = 0;
  for (int k = 1; k < dscx.size(); ++k) {
    static int freq[MAXD];
    memset(freq, 0, sizeof(freq));
    static int f[MAXN];
    int ccnt = 0, maxl = 0;
    for (int l = 1, r = 1; l < dsc.size(); ++l) {
      while (r <= dsc.size() && ccnt < d) {
        for (int i = 0; i < (int)nodey[r].size(); ++i)
          if (nodey[r][i].x <= k) {
            int clr = nodey[r][i].clr;
            if ((++freq[clr]) == 1) ++ccnt;
          }
        ++r;
      }
      if (r > dsc.size()) break;
      f[l] = dsc[r - 1];
      maxl = l;
      for (int i = 0; i < (int)nodey[l].size(); ++i)
        if (nodey[l][i].x <= k) {
          int clr = nodey[l][i].clr;
          if ((--freq[clr]) == 0) --ccnt;
        }
    }
    if (!maxl) continue;
    static int val[MAXN];
    for (int i = 1; i <= maxl; ++i) val[i] = dsc[i] - dsc[i - 1];
    static Segment_Tree tree;
    tree.build(1, 1, maxl, f, val);
    static long long sum[MAXN];
    for (int i = 1; i <= maxl; ++i)
      sum[i] = (sum[i - 1] + (long long)val[i] * (L + 1)) % mod;
    static multiset<int> t[MAXN];
    for (int i = 1; i <= d; ++i) t[i].clear();
    for (int i = 1; i <= n; ++i)
      if (p[i].x <= k) t[p[i].clr].insert(p[i].y);
    for (int i = 1; i <= d; ++i) t[i].insert(0), t[i].insert(dsc.size());
    for (int i = 1; i <= k; ++i) {
      long long now = (sum[maxl] + mod - tree.query(1, 1, maxl, 1, maxl)) % mod;
      ans = (ans +
             now * (dscx[k + 1] - dscx[k]) % mod * (dscx[i] - dscx[i - 1])) %
            mod;
      for (int j = 0; j < (int)nodex[i].size(); ++j) {
        multiset<int> &tt = t[nodex[i][j].clr];
        tt.erase(tt.lower_bound(nodex[i][j].y));
      }
      for (int j = 0; j < (int)nodex[i].size(); ++j) {
        Node &now = nodex[i][j];
        multiset<int> &tt = t[now.clr];
        multiset<int>::iterator it = tt.lower_bound(now.y);
        if (*it == now.y) continue;
        int nxt = dsc[*it];
        --it;
        if ((*it) + 1 <= maxl)
          tree.update(1, 1, maxl, (*it) + 1, min(maxl, now.y), nxt);
      }
    }
  }
  printf("%lld", ans);
  return 0;
}