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;
long long read() {
  char x = getchar();
  long long u = 0, fg = 0;
  while (!isdigit(x)) {
    if (x == '-') fg = 1;
    x = getchar();
  }
  while (isdigit(x)) {
    u = (u << 3) + (u << 1) + (x ^ 48);
    x = getchar();
  }
  return fg ? -u : u;
}
const int maxx = 1e5 + 10, mod = 1e9 + 7;
const int M[3][3] = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
long long n, m, cnt = 0, no[3];
struct node {
  long long pos, val, t;
  bool operator<(const node &X) const {
    return (pos == X.pos) ? (t < X.t) : (pos < X.pos);
  }
} a[maxx];
struct Matrix {
  long long a[3][3];
  Matrix(int c = 0) {
    for (int i = 0; i <= 2; ++i)
      for (int j = 0; j <= 2; ++j) a[i][j] = 0;
    if (c == 8)
      a[0][0] = a[1][1] = a[2][2] = 1;
    else {
      for (int i = 0; i <= 2; ++i, (c >>= 1)) {
        if (!(c & 1)) continue;
        for (int j = 0; j <= 2; ++j) a[i][j] = M[i][j];
      }
    }
  }
  Matrix operator*(const Matrix A) const {
    Matrix tmp;
    for (int k = 0; k <= 2; ++k)
      for (int i = 0; i <= 2; ++i)
        for (int j = 0; j <= 2; ++j) {
          tmp.a[i][j] += a[i][k] * A.a[k][j] % mod;
          tmp.a[i][j] %= mod;
        }
    return tmp;
  }
} matrix;
Matrix qpow(Matrix A, long long k) {
  Matrix ans(8);
  while (k) {
    if (k & 1) ans = ans * A;
    A = A * A;
    k >>= 1;
  }
  return ans;
}
int main() {
  n = read();
  m = read();
  for (int i = (1); i <= (n); ++i) {
    a[++cnt].val = read() - 1;
    a[cnt].pos = read() - 1;
    a[cnt].t = 1;
    a[cnt + 1].val = a[cnt].val;
    a[++cnt].pos = read();
    a[cnt].t = 0;
  }
  sort(a + 1, a + cnt + 1);
  int s = 7;
  a[0].pos = 1;
  matrix.a[1][0] = 1;
  for (int i = (1); i <= (cnt); ++i) {
    Matrix tmp(s);
    matrix = qpow(tmp, a[i].pos - a[i - 1].pos) * matrix;
    if (a[i].t) {
      if (!no[a[i].val]) s ^= (1 << a[i].val);
      ++no[a[i].val];
    } else {
      --no[a[i].val];
      if (!no[a[i].val]) s ^= (1 << a[i].val);
    }
  }
  Matrix tmp(7);
  matrix = qpow(tmp, m - a[cnt].pos) * matrix;
  printf("%lld\n", matrix.a[1][0]);
  return 0;
}
