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;
inline long long myrand(long long l, long long r) {
  long long ret = rand();
  ret <<= 15;
  ret ^= rand();
  if (ret < 0) ret = -ret;
  ret %= (r - l + 1);
  ret += l;
  return ret;
}
template <typename F, typename S>
ostream& operator<<(ostream& os, const pair<F, S>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T> >;
template <typename T>
T max(T a_, T b_, T c_) {
  return max(a_, max(b_, c_));
}
template <typename T>
T min(T a_, T b_, T c_) {
  return min(a_, min(b_, c_));
}
template <typename T>
T min(T a_, T b_, T c_, T d_) {
  return min(min(a_, b_), min(c_, d_));
}
template <typename T>
T max(T a_, T b_, T c_, T d_) {
  return max(max(a_, b_), max(c_, d_));
}
template <typename T>
inline T ceil(T num, T d) {
  return (T)(num / d) + (num % d > (T)0 ? (T)1 : (T)0);
}
long long Matrix_MOD = (1e9 + 7);
struct matrix {
  long long arr[4][4];
  long long row, col;
  matrix() {}
  matrix(long long r, long long c) {
    row = r;
    col = c;
    mem();
  }
  void assign(long long r, long long c) {
    row = r;
    col = c;
  }
  void identity() {
    mem();
    for (long long i = 1; i <= row; i++) arr[i][i] = 1;
  }
  void mem() { memset(arr, 0, sizeof arr); }
  long long* operator[](long long idx) { return arr[idx]; }
  void print() {
    puts("**Printing Starts...**");
    for (long long i = 1; i <= row; i++) {
      for (long long j = 1; j <= col; j++) {
        printf("%lld", arr[i][j]);
        if (j != col) printf(" ");
      }
      puts("");
    }
    puts("**Printing Ends...**");
  }
  matrix operator*(matrix& m) {
    matrix ret(row, m.col);
    for (long long i = 1; i <= ret.row; i++)
      for (long long j = 1; j <= ret.col; j++)
        for (long long k = 1; k <= col; k++)
          ret[i][j] = (ret[i][j] + arr[i][k] * m[k][j]) % Matrix_MOD;
    return ret;
  }
  void operator*=(matrix& m) { *this = *this * m; }
};
matrix matpow(matrix b, long long p) {
  matrix ret(b.row, b.col);
  ret.identity();
  while (p) {
    if (p & 1) ret *= b;
    b *= b;
    p >>= 1;
  }
  return ret;
}
const long long maxn = 100010;
const long long mod = 1e9 + 7;
long long bigmod(long long b, long long p) {
  long long ret = 1;
  while (p) {
    if (p & 1) ret = (ret * b) % mod;
    b = (b * b) % mod;
    p >>= 1;
  }
  return ret;
}
matrix mother, side[4];
void init() {
  mother = matrix(3, 3);
  side[1] = matrix(3, 1);
  side[2] = matrix(3, 1);
  side[3] = matrix(3, 1);
  mother[1][1] = 1;
  mother[1][2] = 1;
  mother[1][3] = 0;
  mother[2][1] = 1;
  mother[2][2] = 1;
  mother[2][3] = 1;
  mother[3][1] = 0;
  mother[3][2] = 1;
  mother[3][3] = 1;
  for (long long i = 1; i <= 3; i++) side[i][i][1] = 1;
}
long long three(long long i, long long j, long long p) {
  matrix ret = matpow(mother, p);
  ret *= side[j];
  return ret[i][1];
}
long long two(long long p) { return bigmod(2, p); }
long long n, m;
long long pre[4][maxn];
long long cell[4][maxn];
long long inv[maxn];
long long upto;
long long height(long long r, long long c) {
  if (cell[r][c]) return 0;
  if (r == 1) {
    long long ret = 1;
    if (cell[2][c] == 0) {
      ret++;
      if (cell[3][c] == 0) ret++;
    }
    return ret;
  }
  if (r == 3) {
    long long ret = 1;
    if (cell[2][c] == 0) {
      ret++;
      if (cell[1][c] == 0) ret++;
    }
    return ret;
  } else {
    long long ret = 1;
    if (cell[1][c] == 0) ret++;
    if (cell[3][c] == 0) ret++;
    return ret;
  }
}
bool valid(long long x, long long y) {
  return 0 < x and x < 4 and 0 < y and y <= upto;
}
vector<tuple<long long, long long, long long> > range;
void compress() {
  vector<long long> v;
  v.push_back(1);
  v.push_back(min(2LL, m));
  v.push_back(m);
  v.push_back(max(1LL, m - 1));
  for (tuple<long long, long long, long long> b : range) {
    long long ro, l, r;
    tie(ro, l, r) = b;
    v.push_back(l - 1);
    v.push_back(l);
    v.push_back(l + 1);
    v.push_back(r - 1);
    v.push_back(r);
    v.push_back(r + 1);
  }
  sort((v).begin(), (v).end());
  (v).erase(unique((v).begin(), (v).end()), v.end());
  map<long long, long long> mp;
  for (long long i = 0; i < v.size(); i++) {
    mp[v[i]] = i + 1;
    inv[i + 1] = v[i];
  }
  upto = v.size();
  for (tuple<long long, long long, long long> b : range) {
    long long ro, l, r;
    tie(ro, l, r) = b;
    pre[ro][mp[l]]++;
    pre[ro][mp[r] + 1]--;
  }
  for (long long i = 1; i <= upto; i++) {
    pre[1][i] += pre[1][i - 1];
    pre[2][i] += pre[2][i - 1];
    pre[3][i] += pre[3][i - 1];
  }
  for (long long i = 1; i <= 3; i++) {
    for (long long j = 1; j <= upto; j++) {
      if (pre[i][j]) cell[i][j] = 1;
    }
  }
}
long long dp[4][maxn];
long long dx[] = {-1, 0, +1};
long long get(long long x, long long y) {
  if (cell[x][y]) return 0;
  if (y == upto) {
    if (x == 2) return 1;
    return 0;
  }
  long long& ret = dp[x][y];
  if (ret != -1) return ret;
  ret = 0;
  long long me = height(x, y), nxt = height(x, y + 1);
  if (me == nxt) {
    long long l = inv[y + 1] - inv[y];
    if (me == 1) {
      ret += get(x, y + 1);
    } else if (me == 2) {
      for (long long i = 0; i < 3; i++) {
        long long xx = dx[i] + x;
        long long yy = y + 1;
        if (valid(xx, yy)) {
          ret += (two(l - 1) * get(xx, yy)) % mod;
        }
      }
    } else if (me == 3) {
      for (long long i = 0; i < 3; i++) {
        long long xx = dx[i] + x;
        long long yy = y + 1;
        if (valid(xx, yy)) {
          ret += (three(x, xx, l) * get(xx, yy)) % mod;
        }
      }
      if (l > 1) {
        if (x == 1) ret += (three(1, 3, l) * get(3, y + 1)) % mod;
        if (x == 3) ret += (three(3, 1, l) * get(1, y + 1)) % mod;
      }
    }
  } else {
    for (long long i = 0; i < 3; i++) {
      long long xx = dx[i] + x;
      long long yy = y + 1;
      if (valid(xx, yy)) {
        ret += get(xx, yy);
      }
    }
  }
  ret %= mod;
  return ret;
}
int32_t main() {
  init();
  memset(dp, -1, sizeof dp);
  cin >> n >> m;
  for (long long i = 1; i <= n; i++) {
    long long ro, l, r;
    cin >> ro >> l >> r;
    range.push_back(tuple<long long, long long, long long>(ro, l, r));
  }
  compress();
  cout << get(2, 1) << '\n';
  return 0;
}
