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;
template <typename T>
istream& operator>>(istream& is, vector<T>& a) {
  for (T& ai : a) is >> ai;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> const& a) {
  os << "[ ";
  for (const T& ai : a) os << ai << " ";
  return os << "]";
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& a) {
  return is >> a.first >> a.second;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2> const& a) {
  return os << "(" << a.first << ", " << a.second << ")";
}
const int M = 1000000007;
struct mat {
  vector<vector<int>> a;
  mat() : a(3, vector<int>(3)) {}
  static mat id() {
    mat r;
    for (int i = 0; i < 3; ++i) r.a[i][i] = 1;
    return r;
  }
  mat operator^(long long n) const {
    mat r = mat::id();
    mat c = *this;
    while (n) {
      if (n & 1) r = r * c;
      if (n >>= 1) c = c * c;
    }
    return r;
  }
  mat operator*(const mat& rhs) const {
    mat r;
    for (int i = 0; i < 3; ++i) {
      for (int j = 0; j < 3; ++j) {
        for (int k = 0; k < 3; ++k) {
          r.a[i][j] = (r.a[i][j] + (long long)a[i][k] * rhs.a[k][j]) % M;
        }
      }
    }
    return r;
  }
};
int f() {
  int n;
  long long m;
  cin >> n >> m;
  vector<mat> t(8);
  for (int s = 0; s < 8; ++s) {
    for (int i = 0; i < 3; ++i)
      for (int j = 0; j < 3; ++j) {
        if (abs(i - j) <= 1 && !((1 << j) & s)) {
          t[s].a[i][j] = 1;
        }
      }
  }
  mat r = mat::id();
  vector<pair<long long, int>> evt;
  long long b, c;
  for (int i = 0, a; i < n; ++i) {
    cin >> a >> b >> c;
    evt.emplace_back(b, a);
    evt.emplace_back(c + 1, -a);
  }
  sort((evt).begin(), (evt).end());
  long long x = 2;
  vector<int> o(3);
  int msk = 0;
  for (const pair<long long, int>& e : evt) {
    if (x < e.first) {
      r = r * (t[msk] ^ (e.first - x));
      x = e.first;
    }
    int a = e.second;
    if (a > 0) {
      if (!o[a - 1]++) msk ^= 1 << (a - 1);
    } else {
      if (!--o[-a - 1]) msk ^= 1 << (-a - 1);
    }
  }
  if (x < m + 1) r = r * (t[0] ^ (m + 1 - x));
  return r.a[1][1];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << f() << "\n";
  return 0;
}
