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;
set<pair<long long, long long> > obs[3];
set<pair<long long, int> > all;
typedef struct mat {
  long long m[3][3];
} Mat;
Mat id;
Mat Mult(Mat& a, Mat& b) {
  Mat ans;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      ans.m[i][j] = 0LL;
      for (int k = 0; k < 3; k++) {
        ans.m[i][j] = (ans.m[i][j] + a.m[i][k] * b.m[k][j]) % 1000000007;
      }
    }
  }
  return ans;
}
Mat MatPow(Mat& a, long long k) {
  if (!k) return id;
  Mat aux = MatPow(a, k / 2);
  aux = Mult(aux, aux);
  return k & 1 ? Mult(aux, a) : aux;
}
int main() {
  long long n, m;
  scanf("%lld %lld", &n, &m);
  for (int i = 0; i < n; i++) {
    long long linha, a, b;
    scanf("%lld %lld %lld", &linha, &a, &b);
    obs[linha - 1].insert(make_pair(a, b));
  }
  for (int i = 0; i < 3; i++) {
    if (obs[i].empty()) continue;
    set<pair<long long, long long> >::iterator it = obs[i].begin();
    while (it != obs[i].end()) {
      long long ini = it->first;
      long long fim = it->second;
      set<pair<long long, long long> >::iterator it2 = it;
      it2++;
      while (it2 != obs[i].end() && it2->first <= fim) {
        fim = max(fim, it2->second);
        obs[i].erase(it2);
        it2 = it;
        it2++;
      }
      obs[i].erase(it);
      obs[i].insert(make_pair(ini, fim));
      it = obs[i].lower_bound(make_pair(ini, fim));
      it++;
    }
  }
  for (int i = 0; i < 3; i++) {
    for (set<pair<long long, long long> >::iterator it = obs[i].begin();
         it != obs[i].end(); it++) {
      all.insert(make_pair(it->first, 0));
      all.insert(make_pair(it->second, 1));
    }
  }
  all.insert(make_pair(m, 1));
  Mat a;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      a.m[i][j] = 1LL;
      id.m[i][j] = (i == j);
    }
  }
  a.m[0][2] = a.m[2][0] = 0LL;
  long long v[] = {0, 1, 0};
  long long last = 2LL;
  bool ok[] = {1, 1, 1};
  for (set<pair<long long, int> >::iterator it = all.begin(); it != all.end();
       it++) {
    long long at = it->second ? it->first : (it->first - 1LL);
    for (int i = 0; i < 3; i++) {
      set<pair<long long, long long> >::iterator it =
          obs[i].lower_bound(make_pair(at + 1, -1));
      if (it == obs[i].begin()) {
        ok[i] = 1;
      } else {
        it--;
        ok[i] = !(it->first <= last && it->second >= last);
      }
    }
    a.m[0][0] = a.m[0][1] = ok[0];
    a.m[1][0] = a.m[1][1] = a.m[1][2] = ok[1];
    a.m[2][1] = a.m[2][2] = ok[2];
    a.m[0][2] = a.m[2][0] = 0LL;
    a = MatPow(a, at - last + 1);
    long long aux[] = {v[0], v[1], v[2]};
    for (int i = 0; i < 3; i++) {
      v[i] = 0LL;
      for (int j = 0; j < 3; j++) {
        v[i] = (v[i] + aux[j] * a.m[i][j]) % 1000000007;
      }
    }
    last = at + 1;
  }
  printf("%lld\n", v[1]);
}
