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;
inline void Fail() {
  printf("0");
  exit(0);
}
const int maxn = 10005;
const int mod = 1e9 + 7;
inline void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
inline int mult(int a, int b) { return 1LL * a * b % mod; }
int n, st[3];
long long m;
map<long long, vector<pair<int, int> > > event;
class matrix {
 public:
  int m[3][3];
  matrix() { memset(m, 0, sizeof(m)); }
  matrix operator*(const matrix &other) const {
    matrix res;
    for (int(i) = 0; (i) < 3; i++)
      for (int(j) = 0; (j) < 3; j++)
        for (int(k) = 0; (k) < 3; k++)
          add(res.m[i][j], mult(m[i][k], other.m[k][j]));
    return res;
  }
};
matrix quick_pow(matrix x, long long power) {
  matrix res;
  for (int(i) = 0; (i) < 3; i++) res.m[i][i] = 1;
  for (; power; power >>= 1LL) {
    if (power & 1) res = res * x;
    x = x * x;
  }
  return res;
}
matrix trans(matrix state, long long pos, long long len) {
  if (len < 0) return state;
  if (event.count(pos))
    for (int(i) = 0; (i) < event[pos].size(); i++)
      st[event[pos][i].first] += event[pos][i].second;
  matrix nst;
  for (int(i) = 0; (i) < 3; i++)
    if (!st[i]) {
      if (i > 0) add(nst.m[i][0], state.m[i - 1][0]);
      add(nst.m[i][0], state.m[i][0]);
      if (i < 2) add(nst.m[i][0], state.m[i + 1][0]);
    }
  if (st[1] || (st[0] && st[2])) return nst;
  if (!st[0] && !st[2]) {
    matrix cur;
    for (int(i) = 0; (i) < 3; i++) {
      if (i > 0) cur.m[i][i - 1] = 1;
      cur.m[i][i] = 1;
      if (i < 2) cur.m[i][i + 1] = 1;
    }
    nst = quick_pow(cur, len) * nst;
  } else if (st[2]) {
    assert(!st[0]);
    matrix cur;
    for (int(i) = 0; (i) < 2; i++)
      for (int(j) = 0; (j) < 2; j++) cur.m[i][j] = 1;
    nst = quick_pow(cur, len) * nst;
  } else {
    assert(!st[2]);
    matrix cur;
    for (int(i) = 1; (i) <= 2; i++)
      for (int(j) = 1; (j) <= 2; j++) cur.m[i][j] = 1;
    nst = quick_pow(cur, len) * nst;
  }
  return nst;
}
int main() {
  scanf("%d%I64d", &n, &m);
  m--;
  for (int(i) = 0; (i) < n; i++) {
    int a;
    long long l, r;
    scanf("%d%I64d%I64d", &a, &l, &r);
    a--;
    l--;
    r--;
    event[l].push_back(make_pair(a, 1));
    event[r + 1].push_back(make_pair(a, -1));
  }
  matrix cur;
  cur.m[1][0] = 1;
  cur = trans(cur, 0, event.begin()->first - 2);
  for (map<long long, vector<pair<int, int> > >::iterator it = event.begin();
       it != event.end(); it++) {
    map<long long, vector<pair<int, int> > >::iterator it2 = it;
    it2++;
    long long nxt = (it2 == event.end() ? m + 1 : it2->first);
    cur = trans(cur, it->first, nxt - it->first - 1);
  }
  printf("%d", cur.m[1][0]);
  return 0;
}
