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 long long MOD = 1e9 + 7;
long long s[3];
long long n, m;
struct Data {
  long long a, l, r;
  Data() {}
  Data(long long a, long long l, long long r) : a(a), l(l), r(r) {}
} p[10000 + 10];
bool cmp(const Data& data1, const Data& data2) { return data1.l < data2.l; }
vector<vector<long long> > mul(vector<vector<long long> > A,
                               vector<vector<long long> > B) {
  vector<vector<long long> > C(3, vector<long long>(3));
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
      }
    }
  }
  return C;
}
vector<vector<long long> > pow(vector<vector<long long> > A, long long n) {
  vector<vector<long long> > B(3, vector<long long>(3));
  for (int i = 0; i < 3; i++) B[i][i] = 1;
  while (n > 0) {
    if (n & 1) B = mul(B, A);
    A = mul(A, A);
    n >>= 1;
  }
  return B;
}
inline bool empty() { return (s[0] == -1 && s[1] == -1 && s[2] == -1); }
inline pair<long long, long long> getmin() {
  pair<long long, long long> p = make_pair(-1, -1);
  for (int i = 0; i < 3; i++) {
    if (s[i] > 0 && (p.first == -1 || s[i] < p.first))
      p = make_pair(s[i], i + 3);
  }
  return p;
}
long long solve() {
  sort(p, p + n, cmp);
  s[0] = s[1] = s[2] = -1;
  vector<pair<long long, long long> > v;
  vector<vector<long long> > A(3, vector<long long>(3, 1)),
      res(3, vector<long long>(3, 0));
  A[0][2] = A[2][0] = 0;
  res[0][0] = res[1][1] = res[2][2] = 1;
  for (int i = 0; i < n || !empty(); i++) {
    while (!empty()) {
      pair<long long, long long> pr = getmin();
      if (i >= n || pr.first < p[i].l) {
        v.push_back(pr);
        s[pr.second - 3] = -1;
      } else {
        break;
      }
    }
    if (i < n) {
      if (s[p[i].a] == -1) v.push_back(make_pair(p[i].l, p[i].a));
      s[p[i].a] = max(s[p[i].a], p[i].r);
    }
  }
  long long k = 1;
  for (int i = 0; i <= v.size(); i++) {
    long long nxt = i < v.size() ? v[i].first : m;
    res = mul(pow(A, nxt - k), res);
    k = nxt;
    if (i < v.size()) {
      if (v[i].second >= 3) {
        v[i].second -= 3;
        for (int j = 0; j < 3; j++) A[v[i].second][j] = 1;
        if (v[i].second % 2 == 0) A[v[i].second][2 - v[i].second] = 0;
      } else {
        for (int j = 0; j < 3; j++) A[v[i].second][j] = 0;
      }
    }
  }
  return res[1][1];
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> p[i].a >> p[i].l >> p[i].r;
    p[i].a--;
    p[i].l--;
  }
  cout << solve() << endl;
  return 0;
}
