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;
static char buf[100000], *p1 = buf, *p2 = buf;
static const int MAXN = 1e5 + 10;
static const int OO = 0x3fffffff;
static const long long mod = 1e9 + 7;
long long read() {
  long long ret = 0;
  char ch =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (ch < '0' || ch > '9')
    ch = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
              ? EOF
              : *p1++);
  while (ch >= '0' && ch <= '9')
    ret = ret * 10 + ch - '0',
    ch = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
              ? EOF
              : *p1++);
  return ret;
}
class Matrix {
 public:
  Matrix() {
    matrix_row = matrix_column = 3;
    clear();
  }
  int matrix_row, matrix_column;
  long long matrix[5][5];
  void clear() { memset(matrix, 0, sizeof(matrix)); }
  void transform_matrix() {
    for (register int i = 1; i <= matrix_row; ++i) {
      for (register int j = 1; j <= matrix_column; ++j) {
        matrix[i][j] = 1;
      }
    }
    matrix[1][3] = matrix[3][1] = 0;
  }
  void identity() {
    clear();
    for (int i = 1; i <= matrix_row; ++i) matrix[i][i] = 1;
  }
  Matrix operator*(const Matrix& x) const {
    Matrix res;
    res.matrix_row = this->matrix_row;
    res.matrix_column = x.matrix_column;
    res.clear();
    for (register int i = 1; i <= this->matrix_row; ++i) {
      for (register int j = 1; j <= x.matrix_column; ++j) {
        for (register int k = 1; k <= this->matrix_column; ++k) {
          res.matrix[i][j] =
              (res.matrix[i][j] + this->matrix[i][k] * x.matrix[k][j] % mod) %
              mod;
        }
      }
    }
    return res;
  }
  Matrix quick_pow(Matrix x, long long b) {
    Matrix res;
    res.identity();
    while (b) {
      if (b & 1) res = res * x;
      x = x * x;
      b >>= 1;
    }
    return res;
  }
};
int n;
long long m;
long long v[MAXN];
int cnt;
int bad[4][MAXN];
int main() {
  scanf("%d%lld", &n, &m);
  vector<tuple<int, long long, long long> > till;
  for (int i = 1; i <= n; ++i) {
    int row;
    long long l, r;
    scanf("%d%lld%lld", &row, &l, &r);
    v[++cnt] = l - 1;
    v[++cnt] = r;
    till.push_back(tie(row, l, r));
  }
  v[++cnt] = 1;
  v[++cnt] = m;
  sort(v + 1, v + 1 + cnt);
  int nn = unique(v + 1, v + 1 + cnt) - (v + 1);
  for (int i = 1; i <= n; ++i) {
    int row;
    long long l, r;
    tie(row, l, r) = till[i - 1];
    long long _l = lower_bound(v + 1, v + 1 + nn, l) - v;
    long long _r = lower_bound(v + 1, v + 1 + nn, r) - v;
    ++bad[row][_l];
    --bad[row][_r + 1];
  }
  Matrix ans;
  ans.clear();
  ans.matrix[2][1] = 1ll;
  long long now[4];
  memset(now, 0, sizeof(now));
  for (int i = 2; i <= nn; ++i) {
    long long len = v[i] - v[i - 1];
    Matrix tp;
    tp.transform_matrix();
    for (int j = 1; j <= 3; ++j) {
      now[j] += bad[j][i];
      if (now[j]) {
        tp.matrix[j][1] = tp.matrix[j][2] = tp.matrix[j][3] = 0;
      }
    }
    tp = tp.quick_pow(tp, len);
    ans = tp * ans;
  }
  printf("%lld\n", ans.matrix[2][1]);
  return 0;
}
