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 i, i1, j, k, k1, t, n, m, res, check1, a, b, c, mt[3][3], pv[3][3],
    mod, x, stat[3];
long long st[3][3] = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
long long pt[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
vector<pair<long long, long long>> v;
vector<long long> o;
void fmexp(long long x) {
  long long i, j, k;
  o.clear();
  while (x > 1) {
    if (x % 2 == 1) {
      o.push_back(1);
    }
    x /= 2;
    o.push_back(2);
  }
  reverse(o.begin(), o.end());
  for (i = 0; i < 3; i++) {
    for (j = 0; j < 3; j++) {
      mt[i][j] = st[i][j];
    }
  }
  for (auto u : o) {
    for (i = 0; i < 3; i++) {
      for (j = 0; j < 3; j++) {
        pv[i][j] = mt[i][j];
      }
    }
    if (u == 2) {
      for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
          mt[i][j] = 0;
          for (k = 0; k < 3; k++) {
            mt[i][j] = (mt[i][j] + pv[i][k] * pv[k][j]) % mod;
          }
        }
      }
    } else {
      for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
          mt[i][j] = 0;
          for (k = 0; k < 3; k++) {
            mt[i][j] = (mt[i][j] + pv[i][k] * st[k][j]) % mod;
          }
        }
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  mod = 1000000007;
  cin >> n >> m;
  for (i = 0; i < n; i++) {
    cin >> a >> b >> c;
    v.push_back({b, a});
    v.push_back({c + 1, a + 3});
  }
  for (i = 0; i < 3; i++) stat[i] = 0;
  v.push_back({2, -1});
  v.push_back({m + 1, 0});
  sort(v.begin(), v.end());
  for (i = 1; i < v.size(); i++) {
    k = v[i].first - v[i - 1].first;
    x = v[i].second - 1;
    if (k != 0) {
      fmexp(k);
      for (i1 = 0; i1 < 3; i1++) {
        for (j = 0; j < 3; j++) {
          pv[i1][j] = pt[i1][j];
        }
      }
      res = 0;
      for (i1 = 0; i1 < 3; i1++) {
        for (j = 0; j < 3; j++) {
          pt[i1][j] = 0;
          for (k = 0; k < 3; k++) {
            pt[i1][j] = (pt[i1][j] + mt[i1][k] * pv[k][j]) % mod;
          }
        }
      }
    }
    if (x < 3) {
      stat[x]++;
      for (j = 0; j < 3; j++) {
        st[x][j] = 0;
      }
    } else {
      stat[x - 3]--;
      if (stat[x - 3] == 0) {
        for (j = 0; j < 3; j++) {
          if (x + j != 5 || x == 4) {
            st[x - 3][j] = 1;
          } else {
            st[x - 3][j] = 0;
          }
        }
      }
    }
  }
  cout << pt[1][1];
  return 0;
}
