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;
map<long long int, long long int> mp;
long long int n, m, a[5][100005], c[100005], l[100005], r[100005], b[100005];
vector<long long int> vt;
vector<vector<long long int> > mul(const vector<vector<long long int> > &A,
                                   const vector<vector<long long int> > &B) {
  vector<vector<long long int> > C(5, vector<long long int>(5));
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= 3; j++)
      for (int k = 1; k <= 3; k++)
        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % 1000000007;
  return C;
}
vector<vector<long long int> > pow(const vector<vector<long long int> > &A,
                                   long long int p) {
  if (p == 1) return A;
  if (p % 2) return mul(A, pow(A, p - 1));
  vector<vector<long long int> > X = pow(A, p / 2);
  return mul(X, X);
}
vector<long long int> F(5);
vector<long long int> G(5);
vector<vector<long long int> > T(5, vector<long long int>(5));
void process(long long int now, long long int next) {
  if (a[1][mp[now]])
    G[1] = 0;
  else
    G[1] = (F[1] + F[2]) % 1000000007;
  if (a[2][mp[now]])
    G[2] = 0;
  else
    G[2] = (F[1] + F[2] + F[3]) % 1000000007;
  if (a[3][mp[now]])
    G[3] = 0;
  else
    G[3] = (F[3] + F[2]) % 1000000007;
  bool one = true, two = true, three = true;
  if (now - 1 == next) {
    F[1] = G[1], F[2] = G[2], F[3] = G[3];
    return;
  }
  if (a[1][mp[now]] && a[1][mp[next]]) one = false;
  if (a[2][mp[now]] && a[2][mp[next]]) two = false;
  if (a[3][mp[now]] && a[3][mp[next]]) three = false;
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= 3; j++) T[i][j] = 1;
  T[1][3] = T[3][1] = 0;
  F[1] = F[2] = F[3] = 0;
  if (one && two && three) {
    if (next + 1 < now) {
      T = pow(T, now - next - 1);
      for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
          F[j] = (F[j] + G[i] * T[j][i]) % 1000000007;
    }
  } else if (one && two) {
    T[2][3] = T[3][2] = T[3][3] = 0;
    if (next + 1 < now) {
      T = pow(T, now - next - 1);
      for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
          F[j] = (F[j] + G[i] * T[j][i]) % 1000000007;
    }
  } else if (two && three) {
    T[1][1] = T[1][2] = T[2][1] = 0;
    if (next + 1 < now) {
      T = pow(T, now - next - 1);
      for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
          F[j] = (F[j] + G[i] * T[j][i]) % 1000000007;
    }
  } else if (one && three) {
    F[1] = G[1] + G[2], F[3] = G[3] + G[2];
  } else if (one) {
    F[1] = G[1] + G[2];
  } else if (two) {
    F[2] = G[2] + G[1] + G[3];
  } else if (three) {
    F[3] = G[3] + G[2];
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  scanf("%lld%lld", &n, &m);
  vt.push_back(1);
  vt.push_back(m);
  vt.push_back(m - 1);
  for (int i = 1; i <= n; i++) {
    scanf("%lld%lld%lld", &c[i], &l[i], &r[i]);
    vt.push_back(l[i]);
    if (l[i] > 1) vt.push_back(l[i] - 1);
    vt.push_back(l[i] + 1);
    vt.push_back(r[i]);
    if (r[i] > 1) vt.push_back(r[i] - 1);
    vt.push_back(r[i] - 1);
  }
  sort(vt.begin(), vt.end());
  long long int cnt = 1;
  for (int i = 0; i < vt.size(); i++)
    if (!mp[vt[i]]) {
      mp[vt[i]] = cnt;
      b[cnt] = vt[i];
      cnt++;
    }
  for (int i = 1; i <= n; i++) {
    a[c[i]][mp[l[i]]]++;
    a[c[i]][mp[r[i]] + 1]--;
  }
  for (int i = 1; i <= cnt; i++) {
    a[1][i] += a[1][i - 1], a[2][i] += a[2][i - 1], a[3][i] += a[3][i - 1];
  }
  F[1] = F[3] = 0, F[2] = 1;
  for (int i = cnt - 2; i > 1; i--) {
    process(b[i], b[i - 1]);
  }
  F[1] = (F[1] + F[2] + F[3]) % 1000000007;
  printf("%lld\n", F[1]);
  return 0;
}
