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 = 1000000007;
vector<vector<long long>> multi(vector<vector<long long>> &a,
                                vector<vector<long long>> &b) {
  vector<vector<long long>> ans(a.size(), vector<long long>(b[0].size(), 0));
  for (int i = 0; i < a.size(); i++) {
    for (int j = 0; j < b[0].size(); j++) {
      for (int k = 0; k < a[0].size(); k++) {
        ans[i][j] = (ans[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
      }
    }
  }
  return ans;
}
vector<vector<long long>> expo(vector<vector<long long>> x, long long n) {
  if (n == 0) {
    vector<vector<long long>> ret(x.size(), vector<long long>(x.size(), 0));
    for (int i = 0; i < x.size(); i++) {
      ret[i][i] = 1;
    }
    return ret;
  }
  vector<vector<long long>> ans = expo(x, n / 2);
  ans = multi(ans, ans);
  if (n % 2 == 1) ans = multi(ans, x);
  return ans;
}
void printMat(vector<vector<long long>> &mat) {
  for (int i = 0; i < mat.size(); i++) {
    for (int j = 0; j < mat[i].size(); j++) {
      cout << mat[i][j] << " ";
    }
    cout << "\n";
  }
}
struct Obs {
  long long a, l, r;
};
struct Node {
  long long index;
  long long row;
  long long col;
  bool start;
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long n, m;
  cin >> n >> m;
  vector<Obs> obs(n);
  for (int i = 0; i < n; i++) {
    cin >> obs[i].a >> obs[i].l >> obs[i].r;
    obs[i].a--;
  }
  auto cmp = [](const Node &l, const Node &r) { return l.col < r.col; };
  multiset<Node, decltype(cmp)> cur(cmp);
  for (int i = 0; i < obs.size(); i++) {
    cur.insert({i, obs[i].a, obs[i].l, true});
    cur.insert({i, obs[i].a, obs[i].r + 1, false});
  }
  map<long long, vector<long long>> locked;
  locked[2] = {0, 0, 0};
  while (!cur.empty()) {
    Node node = *cur.begin();
    cur.erase(cur.begin());
    if (locked.find(node.col) == locked.end()) {
      locked[node.col] = locked.rbegin()->second;
    }
    locked[node.col][node.row] += (node.start ? +1 : -1);
  }
  locked[m + 1] = {0, 0, 0};
  vector<vector<long long>> ans = {{0, 1, 0}};
  for (auto x : locked) {
    long long n;
    if (locked.upper_bound(x.first) == locked.end()) {
      break;
    } else {
      auto iter = locked.upper_bound(x.first);
      long long next = iter->first - 1;
      n = next - x.first + 1;
    }
    vector<vector<long long>> exp;
    exp = {{1, 1, 0},
           {
               1,
               1,
               1,
           },
           {0, 1, 1}};
    for (int i = 0; i < x.second.size(); i++) {
      if (x.second[i] > 0) {
        exp[0][i] = exp[1][i] = exp[2][i] = 0;
      }
    }
    exp = expo(exp, n);
    ans = multi(ans, exp);
  }
  cout << ans[0][1] << "\n";
  return 0;
}
