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 double pi = acos(-1.0);
const double eps = 1e-11;
template <class T>
inline void ckmin(T& a, T b) {
  a = min(a, b);
}
template <class T>
inline void ckmax(T& a, T b) {
  a = max(a, b);
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
using uint = unsigned int;
using int64 = long long;
using uint64 = unsigned long long;
using ipair = pair<int, int>;
using VI = vector<int>;
using VD = vector<double>;
template <typename ModWrapper>
class Modular {
 public:
  using base_type = typename decay<decltype(ModWrapper::value)>::type;
  base_type n;
  Modular(long long d = 0) {
    n = (d >= 0 ? d % mod() : (d % mod() + mod()) % mod());
  }
  static base_type mod() { return ModWrapper::value; }
  base_type val() const { return n; }
  Modular operator-() const { return build(n == 0 ? 0 : mod() - n); }
  Modular& operator+=(Modular a) {
    n = (n >= mod() - a.n ? n - mod() + a.n : n + a.n);
    return *this;
  }
  Modular& operator-=(Modular a) {
    n = (n >= a.n) ? n - a.n : n - a.n + mod();
    return *this;
  }
  Modular& operator*=(Modular a) {
    *this = *this * a;
    return *this;
  }
  Modular& operator/=(Modular a) {
    *this = *this / a;
    return *this;
  }
  static Modular build(base_type n) {
    Modular r;
    r.n = n;
    return r;
  }
  friend Modular inverse(Modular n) { return build(inverse_internal(n.n)); }
  friend bool operator==(Modular a, Modular b) { return a.n == b.n; }
  friend bool operator!=(Modular a, Modular b) { return a.n != b.n; }
  friend Modular operator+(Modular a, Modular b) {
    return build(a.n >= mod() - b.n ? a.n - mod() + b.n : a.n + b.n);
  }
  friend Modular operator-(Modular a, Modular b) {
    return build(a.n >= b.n ? a.n - b.n : a.n - b.n + mod());
  }
  friend Modular operator*(Modular a, Modular b) {
    return build(
        static_cast<base_type>(static_cast<long long>(a.n) * b.n % mod()));
  }
  friend Modular operator/(Modular a, Modular b) { return a * inverse(b); }
  friend Modular pow(Modular p, long long e) {
    if (e <= 0) return Modular(1);
    Modular r = Modular(1);
    while (1) {
      if (e & 1) r *= p;
      e /= 2;
      if (e)
        p = p * p;
      else
        break;
    }
    return r;
  }
  friend istream& operator>>(istream& stream, Modular& a) {
    stream >> a.n;
    return stream;
  }
  friend ostream& operator<<(ostream& stream, const Modular& a) {
    stream << a.n;
    return stream;
  }

 private:
  static constexpr int INVERSE_CACHE_SIZE = (1 << 18);
  static base_type inverse_cache[INVERSE_CACHE_SIZE];
  static base_type inverse_cache_mod_value;
  static base_type inverse_internal(base_type n) {
    if (inverse_cache_mod_value != mod()) {
      inverse_cache_mod_value = mod();
      inverse_cache[0] = 0;
      inverse_cache[1] = 1;
      for (int n = 2; n < INVERSE_CACHE_SIZE; ++n)
        inverse_cache[n] =
            (mod() - (base_type)((long long)inverse_cache[mod() % n] *
                                 (mod() / n) % mod()));
    }
    return n < INVERSE_CACHE_SIZE ? inverse_cache[n]
                                  : inverse_internal_large(n);
  }
  static base_type inverse_internal_large(base_type n) {
    return n < INVERSE_CACHE_SIZE
               ? inverse_cache[n]
               : mod() -
                     (base_type)((long long)inverse_internal_large(mod() % n) *
                                 (mod() / n) % mod());
  }
};
template <typename ModWrapper>
typename decay<decltype(ModWrapper::value)>::type
    Modular<ModWrapper>::inverse_cache[INVERSE_CACHE_SIZE];
template <typename ModWrapper>
typename decay<decltype(ModWrapper::value)>::type
    Modular<ModWrapper>::inverse_cache_mod_value = -1;
using ModType = int;
struct ModWrapper {
  static ModType value;
};
ModType ModWrapper::value = (1000000007);
ModType& mod_value = ModWrapper::value;
using Int = Modular<ModWrapper>;
Int solve(int n) {
  int m, L;
  cin >> m;
  cin >> L;
  VI x(n), y(n), c(n);
  for (int i = 0; i < (n); ++i) {
    cin >> x[i] >> y[i] >> c[i];
    --c[i];
  }
  set<int> sx(x.begin(), x.end()), sy(y.begin(), y.end());
  sx.insert(L);
  sy.insert(L);
  VI lx(sx.begin(), sx.end()), ly(sy.begin(), sy.end());
  map<int, int> mx, my;
  for (int i = 0; i < (((int)lx.size())); ++i) mx[lx[i]] = i;
  for (int i = 0; i < (((int)ly.size())); ++i) my[ly[i]] = i;
  int cx = ((int)lx.size()) - 1;
  int cy = ((int)ly.size()) - 1;
  for (int i = 0; i < (n); ++i) x[i] = mx[x[i]], y[i] = my[y[i]];
  auto prevL = [&](const VI& l, int idx) -> Int {
    return l[idx] - (idx == 0 ? -1 : l[idx - 1]);
  };
  auto nextL = [&](const VI& l, int idx) -> Int { return l[idx + 1] - l[idx]; };
  vector<VI> gx(cx);
  for (int i = 0; i < (n); ++i) gx[x[i]].push_back(i);
  vector<multiset<int>> gc(m);
  Int ret = 0;
  for (int x1 = 0; x1 < (cx); ++x1) {
    for (int i = 0; i < (m); ++i) gc[i].clear();
    for (int i = 0; i < (n); ++i)
      if (x[i] >= x1) gc[c[i]].insert(y[i]);
    map<int, int> pts;
    pts[-1] = 0;
    pts[L] = L + 1;
    Int sum = 0;
    auto eval = [&](ipair a, ipair b) -> Int {
      return (Int)(a.second) * (Int)(b.first - a.first);
    };
    auto add = [&](int s_idx, int val_idx) {
      int s = (s_idx == 0 ? 0 : ly[s_idx - 1] + 1);
      if (s >= L) return;
      int val = ly[val_idx];
      if ((--pts.upper_bound(s))->second >= val) return;
      while (1) {
        auto it = pts.lower_bound(s);
        if (it->second > val) break;
        auto it1 = it;
        --it1;
        auto it2 = it;
        ++it2;
        sum -= eval(*it1, *it);
        sum -= eval(*it, *it2);
        sum += eval(*it1, *it2);
        pts.erase(it);
      }
      {
        auto it2 = pts.upper_bound(s);
        auto it1 = it2;
        --it1;
        sum -= eval(*it1, *it2);
        sum += eval(*it1, make_pair(s, val));
        sum += eval(make_pair(s, val), *it2);
        pts[s] = val;
      }
    };
    for (int i = 0; i < (m); ++i) {
      VI a(gc[i].begin(), gc[i].end());
      if (a.empty())
        add(0, cy);
      else {
        add(0, a[0]);
        add(a.back() + 1, cy);
        for (int i = 0; i < (((int)a.size()) - 1); ++i) add(a[i] + 1, a[i + 1]);
      }
    }
    for (int x2 = cx - 1; x2 >= x1; x2--) {
      ret += ((Int)L * (int)L - sum) * prevL(lx, x1) * nextL(lx, x2);
      if (x2 > x1)
        for (int idx : gx[x2]) {
          int y0 = y[idx];
          int c0 = c[idx];
          gc[c0].erase(gc[c0].find(y0));
          auto it = gc[c0].lower_bound(y0);
          if (it != gc[c0].end() && *it == y0) continue;
          int next = (it == gc[c0].end() ? cy : *it);
          int prev = -1;
          if (it != gc[c0].begin()) {
            --it;
            prev = *it;
          }
          add(prev + 1, next);
        }
    }
  }
  return ret;
}
int main() {
  std::ios::sync_with_stdio(false);
  int n;
  while (cin >> n) {
    Int ret = solve(n);
    printf("%d\n", ret.n);
    break;
  }
  return 0;
}