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;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<ll, ll>;
using vi = vc<ll>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <class t, size_t n>
ostream& operator<<(ostream& os, const array<t, n>& first) {
  return os << vc<t>(first.begin(), first.end());
}
template <ll i, class T>
void print_tuple(ostream&, const T&) {}
template <ll i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
template <class t>
void print(t x, ll suc = 1) {
  cout << x;
  if (suc == 1) cout << "\n";
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(ll n, ll off = 0) {
  vi v(n);
  for (ll i = ll(0); i < ll(n); i++) v[i] = read() + off;
  return v;
}
pi readpi(ll off = 0) {
  ll first, second;
  cin >> first >> second;
  return pi(first + off, second + off);
}
template <class T>
void print(const vector<T>& v, ll suc = 1) {
  for (ll i = ll(0); i < ll(v.size()); i++)
    print(v[i], i == ll(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes"
       << "\n";
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No"
       << "\n";
  if (ex) exit(0);
}
void possible(bool ex = true) {
  cout << "Possible"
       << "\n";
  if (ex) exit(0);
}
void impossible(bool ex = true) {
  cout << "Impossible"
       << "\n";
  if (ex) exit(0);
}
constexpr ll ten(ll n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
ll topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
ll topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
ll botbit(signed first) { return first == 0 ? 32 : __builtin_ctz(first); }
ll botbit(ll first) { return first == 0 ? 64 : __builtin_ctzll(first); }
ll popcount(signed t) { return __builtin_popcount(t); }
ll popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(ll i) { return i && (i & -i) == i; }
ll mask(ll i) { return (ll(1) << i) - 1; }
bool inc(ll first, ll second, ll c) { return first <= second && second <= c; }
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<ll>(l, r)(gen);
}
template <class t>
void myshuffle(vc<t>& first) {
  for (ll i = ll(0); i < ll(ll(first.size())); i++)
    swap(first[i], first[rand_int(0, i)]);
}
template <class t>
ll lwb(const vc<t>& v, const t& first) {
  return lower_bound(v.begin(), v.end(), first) - v.begin();
}
vvc<ll> readGraph(ll n, ll m) {
  vvc<ll> g(n);
  for (ll i = ll(0); i < ll(m); i++) {
    ll first, second;
    cin >> first >> second;
    first--;
    second--;
    g[first].push_back(second);
    g[second].push_back(first);
  }
  return g;
}
vvc<ll> readTree(ll n) { return readGraph(n, n - 1); }
struct modinfo {
  uint mod, root;
};
template <modinfo const& ref>
struct modular {
  static constexpr uint const& mod = ref.mod;
  static modular root() { return modular(ref.root); }
  uint v;
  modular(ll vv = 0) { s(vv % mod + mod); }
  modular& s(uint vv) {
    v = vv < mod ? vv : vv - mod;
    return *this;
  }
  modular operator-() const { return modular() - *this; }
  modular& operator+=(const modular& rhs) { return s(v + rhs.v); }
  modular& operator-=(const modular& rhs) { return s(v + mod - rhs.v); }
  modular& operator*=(const modular& rhs) {
    v = ull(v) * rhs.v % mod;
    return *this;
  }
  modular& operator/=(const modular& rhs) { return *this *= rhs.inv(); }
  modular operator+(const modular& rhs) const { return modular(*this) += rhs; }
  modular operator-(const modular& rhs) const { return modular(*this) -= rhs; }
  modular operator*(const modular& rhs) const { return modular(*this) *= rhs; }
  modular operator/(const modular& rhs) const { return modular(*this) /= rhs; }
  modular pow(ll n) const {
    modular res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  modular inv() const { return pow(mod - 2); }
  friend modular operator+(ll x, const modular& y) { return modular(x) + y; }
  friend modular operator-(ll x, const modular& y) { return modular(x) - y; }
  friend modular operator*(ll x, const modular& y) { return modular(x) * y; }
  friend modular operator/(ll x, const modular& y) { return modular(x) / y; }
  friend ostream& operator<<(ostream& os, const modular& m) {
    return os << m.v;
  }
  friend istream& operator>>(istream& is, modular& m) {
    ll x;
    is >> x;
    m = modular(x);
    return is;
  }
  bool operator<(const modular& r) const { return v < r.v; }
  bool operator==(const modular& r) const { return v == r.v; }
  bool operator!=(const modular& r) const { return v != r.v; }
  explicit operator bool() const { return v; }
};
extern constexpr modinfo base{1000000007, 0};
using mint = modular<base>;
const ll vmax = (1 << 21) + 10;
mint fact[vmax], finv[vmax], invs[vmax];
void initfact() {
  fact[0] = 1;
  for (ll i = ll(1); i < ll(vmax); i++) {
    fact[i] = fact[i - 1] * i;
  }
  finv[vmax - 1] = fact[vmax - 1].inv();
  for (ll i = vmax - 2; i >= 0; i--) {
    finv[i] = finv[i + 1] * (i + 1);
  }
  for (ll i = vmax - 1; i >= 1; i--) {
    invs[i] = finv[i] * fact[i - 1];
  }
}
mint choose(ll n, ll k) { return fact[n] * finv[n - k] * finv[k]; }
mint binom(ll first, ll second) {
  return fact[first + second] * finv[first] * finv[second];
}
mint catalan(ll n) {
  return binom(n, n) - (n - 1 >= 0 ? binom(n - 1, n + 1) : 0);
}
struct Candy {
  ll x, y, c;
  void readinit() {
    cin >> x >> y >> c;
    c--;
  }
};
bool cmpX(const Candy& first, const Candy& second) {
  return first.x < second.x;
}
bool cmpY(const Candy& first, const Candy& second) {
  return first.y > second.y;
}
struct lower_left_region {
  struct P {
    ll x, y;
    bool operator<(const P& rhs) const {
      return x != rhs.x ? x < rhs.x : y > rhs.y;
    }
  };
  set<P> s;
  ll area = 0;
  void add(ll x, ll y) {
    auto itr = s.lower_bound(P{x, y});
    P l{0, 0}, r{0, 0};
    if (itr != s.end()) {
      if (y <= itr->y) return;
      r = *itr;
    }
    P pre = r;
    while (itr != s.begin()) {
      auto p = prev(itr);
      area += p->x * pre.y;
      if (p->y > y) {
        l = *p;
        break;
      }
      area -= p->x * p->y;
      pre = *p;
      s.erase(p);
    }
    s.insert(itr, P{x, y});
    area += x * y;
    area -= l.x * y;
    area -= x * r.y;
  }
};
struct Query {
  ll t, x, y;
};
mint sub(ll lf, vc<Candy> ps, ll K, ll L) {
  sort(ps.begin(), ps.end(), cmpY);
  vc<Query> qs;
  vvc<pi> pos(K, vc<pi>{pi(-1, L)});
  for (const auto& p : ps) {
    auto& cur = pos[p.c];
    qs.push_back({p.y + 1, L, cur.back().second});
    ll f = lwb(cur, pi(p.x, -1));
    for (ll i = ll(f); i < ll(ll(cur.size())); i++) {
      qs.push_back({p.y + 1, cur[i].first, cur[i - 1].second});
    }
    cur.resize(f);
    cur.emplace_back(p.x, p.y);
  }
  lower_left_region llr;
  for (ll c = ll(0); c < ll(K); c++) {
    for (ll i = ll(0); i < ll(ll(pos[c].size())); i++) {
      ll nx = i + 1 < ll(pos[c].size()) ? pos[c][i + 1].first : L;
      llr.add(nx - lf, pos[c][i].second);
    }
  }
  reverse(qs.begin(), qs.end());
  mint ans = 0;
  ll pre = 0;
  for (const auto& q : qs) {
    mint tmp = ((L - lf) * L - llr.area);
    ans += mint(q.t - pre) * tmp;
    llr.add(q.x - lf, q.y);
    pre = q.t;
  }
  return ans;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  ll n, k, l;
  cin >> n >> k >> l;
  vc<Candy> ps(n);
  for (ll i = ll(0); i < ll(n); i++) {
    ps[i].readinit();
  }
  sort(ps.begin(), ps.end(), cmpX);
  ll pre = -1;
  mint ans = 0;
  for (ll i = ll(0); i < ll(n); i++) {
    if (pre < ps[i].x) {
      ans += sub(ps[i].x, vc<Candy>(ps.begin() + i, ps.end()), k, l) *
             (ps[i].x - pre);
      pre = ps[i].x;
    }
  }
  print(ans);
}