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;
const double DINF = numeric_limits<double>::infinity();
const long long MOD = 1e9 + 7;
const double EPS = 1e-7;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mmtw(MOD);
long long rnd(long long x, long long y) {
  static uniform_int_distribution<long long> d;
  return d(mmtw) % (y - x + 1) + x;
}
template <class T>
T fact(T n) {
  if (n == 1) return 1;
  return n * fact(n - 1);
}
using matrix = vector<vector<long long>>;
matrix matrixProduct(const matrix &, const matrix &);
matrix operator*(const matrix &, const matrix &);
matrix binpow(matrix, long long);
void printMatrix(const matrix &);
ostream &operator<<(ostream &, const matrix &);
istream &operator>>(istream &, matrix &);
void assignMatrix(matrix &, long long, long long);
matrix operator*(const matrix &a, const matrix &b) {
  return matrixProduct(a, b);
}
matrix matrixProduct(const matrix &m1, const matrix &m2) {
  if (m1.size() == 0 || m2.size() == 0) return {};
  if (m2.size() != m1[0].size()) return {};
  long long n = m1.size();
  long long m = m2[0].size();
  vector<long long> tmp(m, 0);
  matrix res(n, tmp);
  for (long long i = 0; i < n; ++i) {
    for (long long j = 0; j < m; ++j) {
      for (long long k = 0; k < m2.size(); ++k) {
        res[i][j] = (res[i][j] + m1[i][k] * m2[k][j]) % MOD;
      }
    }
  }
  return res;
}
matrix binpow(matrix a, long long k) {
  if (k == 0) {
    long long n = a.size();
    matrix res;
    assignMatrix(res, n, n);
    for (long long i = 0; i < n; ++i) {
      res[i][i] = 1;
    }
    return res;
  }
  matrix res = a;
  k--;
  while (k) {
    if (k & 1) res = res * a;
    a = a * a;
    k >>= 1;
  }
  return res;
}
ostream &operator<<(ostream &first, const matrix &a) {
  for (long long i = 0; i < a.size(); ++i) {
    if (i != 0) first << "\n";
    for (long long j = 0; j < a[i].size(); ++j) {
      first << a[i][j] << " ";
    }
  }
  return first;
}
istream &operator>>(istream &first, matrix &a) {
  for (long long i = 0; i < a.size(); ++i) {
    for (long long j = 0; j < a[i].size(); ++j) {
      first >> a[i][j];
    }
  }
  return first;
}
void assignMatrix(matrix &a, long long n, long long m) {
  vector<long long> t(m, 0);
  a.assign(n, t);
}
matrix mt[8];
void build() {
  for (long long mask = 0; mask < 8; ++mask) {
    mt[mask] = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
    for (long long i = 0; i < 3; ++i) {
      if (mask & (1 << i)) {
        for (long long j = 0; j < 3; ++j) {
          mt[mask][i][j] = 0;
        }
      }
    }
  }
}
struct ev {
  long long x;
  long long y;
  bool type;
};
bool operator<(const ev &a, const ev &b) { return a.x < b.x; }
const long long MAXN = 1e5 + 5;
long long n;
long long m;
ev a[MAXN * 2];
long long last = 1;
long long pr[3];
matrix res = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
signed main() {
  cin >> n >> m;
  for (long long i = 0; i < n; ++i) {
    long long x, y1qwer, y2;
    cin >> x >> y1qwer >> y2;
    a[i * 2] = {y1qwer, x - 1, 0};
    a[i * 2 + 1] = {y2 + 1, x - 1, 1};
  }
  sort(a, a + (n * 2));
  build();
  for (long long i = 0; i < n * 2; ++i) {
    long long mask = 0;
    if (pr[0]) mask += 1;
    if (pr[1]) mask += 2;
    if (pr[2]) mask += 4;
    res = binpow(mt[mask], a[i].x - last - 1) * res;
    if (a[i].type == 0) {
      pr[a[i].y]++;
    } else {
      pr[a[i].y]--;
    }
    last = a[i].x - 1;
  }
  res = binpow(mt[0], m - last) * res;
  cout << (res[1][1] % MOD) << endl;
}
