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>
struct V {
  int a;
  long long x;
  char on;
} vv[10000 * 2];
int compare(const void *a, const void *b) {
  struct V *u = (struct V *)a;
  struct V *v = (struct V *)b;
  return u->x == v->x ? 0 : u->x < v->x ? -1 : 1;
}
void mult(int aa[][3], int bb[][3], int cc[][3]) {
  int i, j, k;
  for (i = 0; i < 3; i++)
    for (j = 0; j < 3; j++) {
      long long c = 0;
      for (k = 0; k < 3; k++) c += (long long)aa[i][k] * bb[k][j];
      cc[i][j] = c % 1000000007;
    }
}
void power(int aa[][3], int pp[][3], int tt[][3], long long m) {
  if (m == 0) {
    int i, j;
    for (i = 0; i < 3; i++)
      for (j = 0; j < 3; j++) pp[i][j] = i == j;
    return;
  }
  if (m % 2 == 0) {
    power(aa, tt, pp, m / 2);
    mult(tt, tt, pp);
  } else {
    power(aa, pp, tt, m / 2);
    mult(pp, pp, tt);
    mult(tt, aa, pp);
  }
}
void update(int *kk, int *bb, long long m) {
  static int pp[3][3], tt[3][3], kk_[3];
  int aa[3][3] = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
  int i, j;
  for (i = 0; i < 3; i++)
    if (bb[i])
      for (j = 0; j < 3; j++) aa[i][j] = 0;
  power(aa, pp, tt, m);
  for (i = 0; i < 3; i++) {
    long long k = 0;
    for (j = 0; j < 3; j++) k += (long long)pp[i][j] * kk[j];
    kk_[i] = k % 1000000007;
  }
  for (i = 0; i < 3; i++) kk[i] = kk_[i];
}
int main() {
  static int bb[3], kk[3];
  int n, i, j;
  long long m, l, r, x_;
  scanf("%d%lld", &n, &m);
  for (i = 0; i < n; i++) {
    struct V *u;
    int a;
    scanf("%d%lld%lld", &a, &l, &r), a--, l--;
    u = &vv[i * 2 + 0];
    u->a = a, u->x = l;
    u->on = 1;
    u = &vv[i * 2 + 1];
    u->a = a, u->x = r;
    u->on = 0;
  }
  qsort(vv, n * 2, sizeof *vv, compare);
  kk[1] = 1;
  x_ = 1;
  for (i = 0; i < n * 2; i = j) {
    long long x;
    x = vv[i].x;
    update(kk, bb, x - x_);
    for (j = i; j < n * 2 && vv[j].x == x; j++)
      bb[vv[j].a] += vv[j].on ? 1 : -1;
    x_ = x;
  }
  update(kk, bb, m - x_);
  printf("%d\n", kk[1]);
  return 0;
}
