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;
constexpr int inf32 = 0x3f3f3f3f;
constexpr long long inf64 = 0x3f3f3f3f3f3f3f3f;
struct sec {
  int j;
  long long l, r;
  sec() {}
  sec(int j, long long l, long long r) : j(j), l(l), r(r) {}
};
constexpr int mod = 1000000007;
constexpr int N = 3;
struct matrix {
  vector<vector<int> > arr;
  matrix(int first = 0) {
    arr.assign(N, vector<int>(N, 0));
    for (int i = 0; i < (N); ++i) arr[i][i] = first;
  }
  vector<int> &operator[](int i) { return arr[i]; }
  friend matrix operator*(matrix p, matrix q) {
    matrix res;
    for (int t = 0; t < (N); ++t)
      for (int i = 0; i < (N); ++i)
        for (int j = 0; j < (N); ++j)
          res[i][j] = (1ll * p[i][t] * q[t][j] + res[i][j]) % mod;
    return res;
  }
  matrix mypow(long long first) {
    matrix res(1), a(*this);
    for (; first; first >>= 1, a = a * a)
      if (first & 1) res = res * a;
    return res;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  long long m;
  cin >> n >> m;
  vector<sec> a(n);
  vector<long long> d = {1, m};
  for (int i = 0; i < (n); ++i) {
    int j;
    long long l, r;
    cin >> j >> l >> r, --j, --l;
    a[i] = sec(j, l, r);
    d.push_back(l);
    d.push_back(r);
  }
  sort((d).begin(), (d).end());
  d.erase(unique((d).begin(), (d).end()), d.end());
  int sn = (int)((d).size());
  auto find = [&](long long first) {
    return lower_bound((d).begin(), (d).end(), first) - d.begin();
  };
  vector<vector<int> > c(sn, vector<int>(N, 0));
  for (int i = 0; i < (n); ++i) {
    int j = a[i].j;
    long long l = a[i].l;
    long long r = a[i].r;
    l = find(l), r = find(r);
    ++c[l][j], --c[r][j];
  }
  matrix f;
  f[0][1] = 1;
  for (int i = 0; i < (sn - 1); ++i) {
    for (int t = 0; t < (N); ++t) c[i + 1][t] += c[i][t];
    matrix g;
    for (int j = 0; j < (N); ++j)
      for (int t = 0; t < (N); ++t)
        if (!c[i][t])
          if (abs(j - t) <= 1) g[j][t] = 1;
    f = f * g.mypow(d[i + 1] - d[i]);
  }
  cout << f[0][1] << '\n';
  return 0;
}
