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;
int Y[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int X[] = {0, 0, -1, 1, -1, 1, -1, 1};
int DIR4 = 4;
int DIR8 = 8;
long long power(long long a, long long n) {
  if (a == 0) return 0;
  if (a == 1 || n == 0) return 1;
  if (n == 1) return a % 1000000007;
  long long t = power(a, n / 2);
  t = t * t % 1000000007;
  if (n & 1) return t * a % 1000000007;
  return t;
}
void keywordsForAutocompletion() {}
int popcount(long long a) {
  int c = 0;
  while (a) {
    c++;
    a -= a & -a;
  }
  return c;
}
void factorize(int a) {}
void update(int tree[], int idx, int val, int maxval) {
  for (; idx <= maxval; idx += idx & -idx) {
    tree[idx] += val;
  }
}
int read(int tree[], int idx) {
  long long sum = 0;
  for (; idx > 0; idx -= idx & -idx) {
    sum += tree[idx];
  }
  return sum;
}
struct node2 {
  int id, val;
  node2() {
    static int ctx = 1;
    id = ctx++;
  };
  node2(int a, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0) {
    val = a;
  }
};
struct comp2 {
  bool operator()(int a, int b) { return b < a; }
};
bool cmp2(int a, int b) { return b < a; }
struct node {
  long long row, l, r;
  node(){};
  node(long long a, long long b = 0, long long c = 0, int d = 0, int e = 0,
       int f = 0) {
    row = a;
    l = b;
    r = c;
  }
};
struct comp {
  bool operator()(int a, int b) { return b < a; }
};
bool cmp(int a, int b) { return b < a; }
long long n, m, a, b, c, d, k, h, w, x, y, p, q, t, ans[3][3], res, ma, mi, T,
    act = 0, pas = 1, cur, flag, now;
long long uu, vv, ww, l, r;
long long dp, dp2, cnt, sum, sub, sz, lim, tmp, type, add, row, initState[3];
char s[20009], ch;
double f, z, e;
vector<node> inp;
vector<long long> vec;
int seg[3][2 * 20009], mask[2 * 20009];
bool mid[2 * 20009];
long long mat[10][3][3];
set<long long> sett;
map<int, int> mapp;
void print() {}
void print2() {}
void input() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 1; i < n + 1; i++) {
    cin >> row >> l >> r;
    row--;
    sett.insert(l);
    sett.insert(r);
    inp.push_back(node(row, l, r));
  }
}
void inity() {
  sett.insert(2);
  for (auto u : sett) {
    vec.push_back(u);
    if (u + 1 != m && sett.find(u + 1) == sett.end()) {
      vec.push_back(u + 1);
      mid[vec.size() - 1] = true;
    }
  }
  vec.push_back(m);
}
void initXor() {
  for (auto u : inp) {
    seg[u.row][lower_bound(vec.begin(), vec.end(), u.l) - vec.begin()]++;
    seg[u.row][lower_bound(vec.begin(), vec.end(), u.r + 1) - vec.begin()]--;
  }
  for (int i = 0; i < 3; i++)
    for (int j = 1; j < vec.size(); j++) seg[i][j] += seg[i][j - 1];
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < vec.size(); j++)
      mask[j] |= (seg[i][j] > 0 ? (1 << i) : 0);
}
void initMats() {
  for (int mask = 0; mask < 8; mask++) {
    for (int i = 0; i < 3; i++) {
      if (mask & (1 << i)) {
        for (int j = 0; j < 3; j++) mat[mask][i][j] = 0;
      } else {
        for (int j = 0; j < 3; j++) mat[mask][i][0] = (i < 2);
        mat[mask][i][1] = 1;
        mat[mask][i][2] = (i > 0);
      }
    }
  }
}
inline void copy(long long to[3][3], long long from[3][3]) {
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++) to[i][j] = from[i][j];
}
inline void updateAns(long long b[3][3]) {
  long long tmp[3][3] = {0};
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      for (int k = 0; k < 3; k++)
        tmp[i][j] = (b[i][k] * ans[k][j] % 1000000007 + tmp[i][j]) % 1000000007;
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++) ans[i][j] = tmp[i][j];
}
inline void lastCalc() {
  long long tmp[3] = {0};
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      tmp[i] = (ans[i][j] * initState[j] % 1000000007 + tmp[i]) % 1000000007;
  cout << tmp[1] << "\n";
}
inline void mul(long long to[3][3], long long a[3][3], long long b[3][3]) {
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++) to[i][j] = 0;
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      for (int k = 0; k < 3; k++)
        to[i][j] = (a[i][k] * b[k][j] % 1000000007 + to[i][j]) % 1000000007;
}
void expo(long long a[3][3], long long b[3][3], long long n) {
  if (n == 0) {
    memset(b, 0, sizeof(b));
    b[0][0] = b[1][1] = b[2][2] = 1;
    return;
  }
  if (n == 1) {
    copy(b, a);
    return;
  }
  long long c[3][3] = {0};
  expo(a, c, n / 2);
  mul(b, c, c);
  if (n & 1) {
    mul(c, a, b);
    copy(b, c);
  }
}
inline void calc(long long n, int mask) {
  long long a[3][3] = {0}, b[3][3] = {0};
  copy(a, mat[mask]);
  expo(a, b, n);
  updateAns(b);
}
inline void initBegin() {
  initState[1] = 1;
  for (int i = 0; i < 3; i++) ans[i][i] = 1;
}
void solve() {
  inity();
  initXor();
  initMats();
  initBegin();
  int l = 0;
  for (int j = 1; j < vec.size(); j++) {
    while (j < vec.size() && mask[j] == mask[l]) j++;
    if (j < vec.size() && mid[j] == true) {
      calc(vec[j - 1] - vec[l] + 1, mask[j - 1]);
      l = j;
    } else {
      calc((j < vec.size() ? vec[j] : m + 1) - vec[l], mask[j - 1]);
      l = j;
    }
    j--;
  }
  lastCalc();
}
void output() {}
int main() {
  input();
  solve();
  output();
  return 0;
}
