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;
struct matrix {
  int rows, cols;
  vector<vector<long long> > M;
  matrix() {}
  matrix(int r, int c, int val = 0) {
    rows = r;
    cols = c;
    M.resize(rows);
    for (int i = 0; i < rows; i++) M[i].resize(cols, 0);
    if (val != 0) {
      if (rows != cols)
        cout << "Error creating diagonal matrix\n";
      else {
        for (int i = 0; i < rows; i++) M[i][i] = val;
      }
    }
  }
  void assign(long long arr[]) {
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++) M[i][j] = arr[i * cols + j];
  }
  void read() {
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++) cin >> M[i][j];
  }
  void revread() {
    for (int i = rows - 1; i >= 0; i--)
      for (int j = cols - 1; j >= 0; j--) cin >> M[i][j];
  }
  void disp() {
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) cout << M[i][j] << ' ';
      cout << '\n';
    }
  }
  void pow(long long n) { M = (this->fastpow(*this, n)).M; }
  matrix fastpow(matrix& A, long long n) {
    if (n == 0) return matrix(A.rows, A.cols, 1);
    matrix TEMP = fastpow(A, n / 2);
    TEMP.mul(TEMP);
    if (n & 1) TEMP.mul(A);
    return TEMP;
  }
  void add(matrix& B) {
    if (B.rows != rows || B.cols != cols) {
      cout << "Error adding\n";
      return;
    }
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++) M[i][j] = (M[i][j] + B.M[i][j]) % mod;
  }
  void sub(matrix& B) {
    if (B.rows != rows || B.cols != cols) {
      cout << "Error subtracting\n";
      return;
    }
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
        M[i][j] = ((M[i][j] - B.M[i][j]) % mod + mod) % mod;
  }
  void mul(matrix& B) {
    if (cols != B.rows) {
      cout << "Error multiplying\n";
      return;
    }
    vector<vector<long long> > TEMP;
    TEMP.resize(rows);
    for (int i = 0; i < rows; i++) TEMP[i].resize(B.cols, 0);
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < B.cols; j++)
        for (int k = 0; k < cols; k++)
          TEMP[i][j] = (TEMP[i][j] + (M[i][k] * B.M[k][j]) % mod) % mod;
    M = TEMP;
  }
};
long long n, m, pos = 1, state = 0;
vector<long long> seq;
vector<pair<long long, long long> > st, en;
matrix Trans[8];
matrix dp(3, 1);
long long blocked[3];
void prep() {
  matrix temp(3, 3);
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      temp.M[i][j] = 1;
    }
  }
  temp.M[0][2] = 0;
  temp.M[2][0] = 0;
  Trans[0] = temp;
  for (int i = 1; i < 8; i++) {
    int p = i;
    Trans[i] = Trans[0];
    for (int j = 0; j < 3; j++) {
      if (p % 2 == 1) {
        for (int k = 0; k < 3; k++) {
          Trans[i].M[k][j] = 0;
        }
      }
      p /= 2;
    }
  }
  dp.M[0][0] = 0;
  dp.M[1][0] = 1;
  dp.M[2][0] = 0;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  prep();
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    long long a, l, r;
    cin >> a >> l >> r;
    a--;
    seq.push_back(l);
    seq.push_back(r);
    st.push_back({l, a});
    en.push_back({r, a});
  }
  sort(seq.begin(), seq.end());
  seq.resize(distance(seq.begin(), unique(seq.begin(), seq.end())));
  sort(st.begin(), st.end());
  sort(en.begin(), en.end());
  reverse(st.rbegin(), st.rend());
  reverse(en.rbegin(), en.rend());
  reverse(seq.rbegin(), seq.rend());
  while (!seq.empty()) {
    matrix pre = Trans[state];
    pre.pow(seq.back() - pos);
    pre.mul(dp);
    dp = pre;
    set<int> s;
    while (!st.empty() && st.back().first == seq.back()) {
      blocked[st.back().second]++;
      s.insert(st.back().second);
      st.pop_back();
    }
    while (!en.empty() && en.back().first == seq.back()) {
      blocked[en.back().second]--;
      s.insert(en.back().second);
      en.pop_back();
    }
    for (auto u : s) dp.M[u][0] = 0;
    state = 0;
    int mul = 1;
    for (int j = 0; j < 3; j++) {
      if (blocked[j] > 0) {
        dp.M[j][0] = 0;
        state += mul;
      }
      mul *= 2;
    }
    pos = seq.back();
    seq.pop_back();
  }
  matrix pre = Trans[0];
  pre.pow(m - pos);
  pre.mul(dp);
  dp = pre;
  cout << dp.M[1][0];
  return 0;
}
