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;
const int mo = 1000000007;
long long read() {
  long long x = 0, y = 1;
  char c;
  c = getchar();
  while (!isdigit(c)) {
    if (c == '-') y = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return x * y;
}
struct mtx {
  long long a[3][3];
} p[7], ai;
struct xl {
  long long a[3];
} as, tp;
long long nw;
mtx operator*(mtx q, mtx w) {
  int i, j, k;
  mtx as;
  for (i = 0; i < 3; ++i) {
    for (j = 0; j <= 3; ++j) as.a[i][j] = 0;
  }
  for (i = 0; i < 3; ++i) {
    for (j = 0; j < 3; ++j) {
      for (k = 0; k < 3; ++k)
        as.a[i][j] = (as.a[i][j] + q.a[i][k] * w.a[k][j]) % mo;
    }
  }
  return as;
}
mtx ksm(mtx q, long long w) {
  mtx as = ai;
  while (w) {
    if (w & 1) as = as * q;
    q = q * q;
    w >>= 1;
  }
  return as;
}
xl operator*(mtx q, xl w) {
  xl as;
  int i, j;
  as.a[0] = as.a[1] = as.a[2] = 0;
  for (i = 0; i < 3; ++i) {
    for (j = 0; j < 3; ++j) as.a[i] = (as.a[i] + q.a[i][j] * w.a[j]) % mo;
  }
  return as;
}
long long n, m, ct;
long long q[3];
struct node {
  long long wz, bh;
} a[100010];
bool cmp(node q, node w) { return q.wz < w.wz; }
int main() {
  long long i, j, k, l;
  p[0] = (mtx){{1, 1, 0, 1, 1, 1, 0, 1, 1}};
  p[1] = (mtx){{0, 0, 0, 1, 1, 1, 0, 1, 1}};
  p[2] = (mtx){{1, 1, 0, 0, 0, 0, 0, 1, 1}};
  p[3] = (mtx){{1, 1, 0, 1, 1, 1, 0, 0, 0}};
  p[4] = (mtx){{0, 0, 0, 0, 0, 0, 0, 1, 1}};
  p[5] = (mtx){{0, 0, 0, 1, 1, 1, 0, 0, 0}};
  p[6] = (mtx){{1, 1, 0, 0, 0, 0, 0, 0, 0}};
  ai = (mtx){{1, 0, 0, 0, 1, 0, 0, 0, 1}};
  as.a[1] = 1;
  nw = 1;
  long long nxt;
  n = read();
  m = read();
  for (i = 1; i <= n; ++i) {
    j = read();
    k = read();
    --k;
    l = read();
    a[++ct].wz = k;
    a[ct].bh = j;
    a[++ct].wz = l;
    a[ct].bh = -j;
  }
  sort(a + 1, a + ct + 1, cmp);
  a[++ct].wz = m;
  for (i = 1; i <= ct; ++i) {
    nxt = a[i].wz;
    if (q[0] && q[1] && q[2]) {
      putchar('0');
      return 0;
    }
    if (!q[0] && !q[1] && !q[2]) as = ksm(p[0], nxt - nw) * as;
    if (q[0] && !q[1] && !q[2]) as = ksm(p[1], nxt - nw) * as;
    if (!q[0] && q[1] && !q[2]) as = ksm(p[2], nxt - nw) * as;
    if (!q[0] && !q[1] && q[2]) as = ksm(p[3], nxt - nw) * as;
    if (q[0] && q[1] && !q[2]) as = ksm(p[4], nxt - nw) * as;
    if (q[0] && !q[1] && q[2]) as = ksm(p[5], nxt - nw) * as;
    if (!q[0] && q[1] && q[2]) as = ksm(p[6], nxt - nw) * as;
    if (a[i].bh < 0)
      --q[-a[i].bh - 1];
    else if (a[i].bh > 0)
      ++q[a[i].bh - 1];
    nw = nxt;
  }
  cout << as.a[1];
  return 0;
}
