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;
typedef struct obstaculo {
  int linha;
  long long coluna;
  bool fim;
} Obstaculo;
typedef struct corredor {
  vector<bool> linha_livre;
  long long l, r;
} Corredor;
typedef struct mat {
  long long M[3][3];
} Mat;
Mat create_mat(const vector<bool> &linha_livre) {
  Mat m;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      m.M[i][j] = linha_livre[j];
    }
  }
  m.M[0][2] = m.M[2][0] = 0;
  return m;
}
Mat mat_mult(const Mat &a, const Mat &b) {
  Mat c;
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      c.M[i][j] = 0;
      for (int k = 0; k < 3; k++) {
        c.M[i][j] = (c.M[i][j] + a.M[i][k] * b.M[k][j]) % 1000000007;
      }
    }
  }
  return c;
}
void imprime(Mat a) {
  printf("Matriz:\n");
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      printf("%lld ", a.M[i][j]);
    }
    printf("\n");
  }
}
Mat mat_id(int tam) {
  Mat m;
  for (int i = 0; i < tam; i++) {
    for (int j = 0; j < tam; j++) {
      m.M[i][j] = (i == j);
    }
  }
  return m;
}
Mat mat_pow(const Mat &a, long long k) {
  if (!k) return mat_id(3);
  Mat aux = mat_pow(a, k / 2);
  aux = mat_mult(aux, aux);
  return k & 1 ? mat_mult(a, aux) : aux;
}
Corredor create_corredor(const vector<int> &num_obs, long long l, long long r) {
  Corredor c;
  for (int i = 0; i < 3; i++) {
    c.linha_livre.push_back(num_obs[i] == 0);
  }
  c.l = l;
  c.r = r;
  return c;
}
bool operator<(const Obstaculo &a, const Obstaculo &b) {
  return a.coluna < b.coluna;
}
int main() {
  long long n, m;
  scanf("%lld %lld", &n, &m);
  vector<Obstaculo> obstaculos;
  for (int i = 0; i < n; i++) {
    int a;
    long long l, r;
    scanf("%d %lld %lld", &a, &l, &r);
    Obstaculo o;
    o.linha = a - 1;
    o.coluna = l;
    o.fim = false;
    obstaculos.push_back(o);
    o.coluna = r + 1;
    o.fim = true;
    obstaculos.push_back(o);
  }
  sort(obstaculos.begin(), obstaculos.end());
  vector<Corredor> corredores;
  vector<int> num_obs = {0, 0, 0};
  corredores.push_back(create_corredor(num_obs, 1, obstaculos[0].coluna - 1));
  for (int i = 0; i < obstaculos.size(); i++) {
    num_obs[obstaculos[i].linha] += obstaculos[i].fim ? -1 : 1;
    int j = i + 1;
    while (j < obstaculos.size() &&
           obstaculos[i].coluna == obstaculos[j].coluna) {
      num_obs[obstaculos[j].linha] += obstaculos[j].fim ? -1 : 1;
      j++;
    }
    long long l = obstaculos[i].coluna;
    long long r = (j < obstaculos.size()) ? obstaculos[j].coluna : m;
    corredores.push_back(create_corredor(num_obs, l, r));
    i = j - 1;
  }
  vector<long long> v = {1, 1, 1};
  for (int i = 0; i < corredores.size(); i++) {
    Mat m = create_mat(corredores[i].linha_livre);
    m = mat_pow(m, corredores[i].r - corredores[i].l);
    long long aux[] = {v[0], v[1], v[2]};
    for (int j = 0; j < 3; j++) {
      v[j] = 0;
      for (int k = 0; k < 3; k++) {
        v[j] = (v[j] + m.M[j][k] * aux[k]) % 1000000007;
      }
    }
  }
  printf("%lld\n", v[1]);
}
