You are running through a rectangular field. This field can be represented as a matrix with 3 rows and m columns. (i, j) denotes a cell belonging to i-th row and j-th column.

You start in (2, 1) and have to end your path in (2, m). From the cell (i, j) you may advance to:

  * (i - 1, j + 1) — only if i > 1, 
  * (i, j + 1), or 
  * (i + 1, j + 1) — only if i < 3. 



However, there are n obstacles blocking your path. k-th obstacle is denoted by three integers ak, lk and rk, and it forbids entering any cell (ak, j) such that lk ≤ j ≤ rk.

You have to calculate the number of different paths from (2, 1) to (2, m), and print it modulo 109 + 7.

Input

The first line contains two integers n and m (1 ≤ n ≤ 104, 3 ≤ m ≤ 1018) — the number of obstacles and the number of columns in the matrix, respectively.

Then n lines follow, each containing three integers ak, lk and rk (1 ≤ ak ≤ 3, 2 ≤ lk ≤ rk ≤ m - 1) denoting an obstacle blocking every cell (ak, j) such that lk ≤ j ≤ rk. Some cells may be blocked by multiple obstacles.

Output

Print the number of different paths from (2, 1) to (2, m), taken modulo 109 + 7. If it is impossible to get from (2, 1) to (2, m), then the number of paths is 0.

Example

Input

2 5
1 3 4
2 2 3


Output

2
#include <bits/stdc++.h>
using namespace std;
long long MODULO = 1000000007;
template <size_t N, size_t M, size_t K>
array<array<long long, K>, N> multiply(array<array<long long, M>, N> a,
                                       array<array<long long, K>, M> b) {
  array<array<long long, K>, N> ans;
  for (int n = 0; n < N; ++n) {
    for (int k = 0; k < K; ++k) {
      ans[n][k] = 0;
      for (int m = 0; m < M; ++m) {
        ans[n][k] = (ans[n][k] + a[n][m] * b[m][k]) % MODULO;
      }
    }
  }
  return ans;
}
array<array<long long, 3>, 3> E = {{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}};
struct Ev {
  array<int, 3> t;
  long long x;
  Ev(array<int, 3> t, long long x) : t(t), x(x) {}
  bool operator<(Ev e) const { return x < e.x || (x == e.x && t > e.t); }
};
template <size_t M>
array<array<long long, M>, M> pow(array<array<long long, M>, M> A,
                                  long long x) {
  if (x == 0) {
    return E;
  }
  if (x == 1) {
    return A;
  }
  auto As = pow(A, x / 2);
  return multiply(multiply(As, As), pow(A, x % 2));
}
template <class T1, class T2, size_t M>
array<T1, M> operator+(array<T1, M> a, array<T2, M> b) {
  array<T1, M> ans;
  for (int i = 0; i < M; ++i) {
    ans[i] = a[i] + b[i];
  }
  return ans;
}
array<array<long long, 3>, 3> FULL_STEP = {{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}}};
array<array<long long, 3>, 3> step_matrix(array<int, 3> raw) {
  auto ans = FULL_STEP;
  for (int i = 0; i < 3; ++i) {
    if (raw[i] > 0) {
      for (int j = 0; j < 3; ++j) {
        ans[i][j] = 0;
      }
    }
  }
  return ans;
}
int main() {
  int n;
  cin >> n;
  long long m;
  cin >> m;
  vector<Ev> e;
  for (int i = 0; i < n; ++i) {
    int a;
    long long l, r;
    cin >> a >> l >> r;
    --a;
    ++r;
    array<int, 3> tl = {0, 0, 0};
    tl[a] = 1;
    array<int, 3> tr = {0, 0, 0};
    tr[a] = -1;
    e.emplace_back(tl, l);
    e.emplace_back(tr, r);
  }
  sort(e.begin(), e.end());
  for (int i = 1; i < e.size(); ++i) {
    e[i].t = e[i - 1].t + e[i].t;
  }
  if (e[0].x > 2) {
    e.insert(e.begin(), Ev(array<int, 3>({0, 0, 0}), 2));
  }
  e.emplace_back(array<int, 3>({0, 0, 0}), m + 1);
  vector<Ev> ue;
  for (int i = 0; i < e.size(); ++i) {
    if (i == e.size() - 1 || e[i].x < e[i + 1].x) {
      ue.push_back(e[i]);
    }
  }
  array<array<long long, 1>, 3> ans = {{{0}, {1}, {0}}};
  for (int i = 0; i < ue.size() - 1; ++i) {
    auto step = step_matrix(ue[i].t);
    long long n_steps = ue[i + 1].x - ue[i].x;
    auto powed = pow(step, n_steps);
    ans = multiply(powed, ans);
  }
  cout << ans[1][0] << endl;
  return 0;
}
