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 int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3fll;
const int MAX = 1e4 + 5;
const int MOD = 1e9 + 7;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <class T>
inline void read(T &num) {
  bool start = false, neg = false;
  char c;
  num = 0;
  while ((c = getchar()) != EOF) {
    if (c == '-')
      start = neg = true;
    else if (c >= '0' && c <= '9') {
      start = true;
      num = num * 10 + c - '0';
    } else if (start)
      break;
  }
  if (neg) num = -num;
}
inline long long powMM(long long a, long long b, long long M) {
  long long ret = 1;
  a %= M;
  while (b) {
    if (b & 1) ret = ret * a % M;
    b >>= 1;
    a = a * a % M;
  }
  return ret;
}
void open() {
  freopen("in2.txt", "r", stdin);
  freopen("out2.txt", "w", stdout);
}
const int m_num = 5;
inline void add(int &a, int b) {
  a = (1LL * a + b + MOD) % MOD;
  if (a < 0) a += MOD;
}
long long inv(long long a, long long m) {
  if (a == 1) return 1;
  return inv(m % a, m) * (m - m / a) % m;
}
struct matrix {
  int e[m_num][m_num];
  int row, col;
  matrix() {}
  matrix(int _r, int _c) : row(_r), col(_c) { memset(e, 0, sizeof(e)); }
  matrix operator*(const matrix &tem) const {
    matrix ret = matrix(row, tem.col);
    for (int i = 1; i <= ret.row; i++)
      for (int j = 1; j <= ret.col; j++)
        for (int k = 1; k <= col; k++)
          add(ret.e[i][j], 1LL * e[i][k] * tem.e[k][j] % MOD);
    return ret;
  }
  matrix operator+(const matrix &tem) const {
    matrix ret = matrix(row, col);
    for (int i = 1; i <= row; i++)
      for (int j = 1; j <= col; j++)
        add(ret.e[i][j], (e[i][j] + tem.e[i][j]) % MOD);
    return ret;
  }
  void getE() {
    for (int i = 1; i <= row; i++)
      for (int j = 1; j <= col; j++) e[i][j] = (i == j ? 1 : 0);
  }
  int det(int n) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) e[i][j] = (e[i][j] % MOD + MOD) % MOD;
    int res = 1;
    for (int i = 1; i <= n; i++) {
      for (int j = i; j <= n; j++)
        if (e[j][i] != 0) {
          for (int k = i; k <= n; k++) swap(e[i][k], e[j][k]);
          if (i != j) res = (-res + MOD) % MOD;
          break;
        }
      if (e[i][i] == 0) {
        res = -1;
        break;
      }
      for (int j = i + 1; j <= n; j++) {
        int mut = (e[j][i] * inv(e[i][i], MOD)) % MOD;
        for (int k = i; k <= n; k++)
          e[j][k] = (e[j][k] - (e[i][k] * mut) % MOD + MOD) % MOD;
      }
      res = (res * e[i][i]) % MOD;
    }
    return res;
  }
  long long Det(int n, int mod) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        e[i][j] %= mod;
      }
    }
    long long res = 1;
    for (int i = 1; i <= n; ++i) {
      if (!e[i][i]) {
        bool flag = false;
        for (int j = i + 1; j <= n; ++j) {
          if (e[j][i]) {
            flag = true;
            for (int k = i; k <= n; ++k) {
              swap(e[i][k], e[j][k]);
            }
            res = -res;
            break;
          }
        }
        if (!flag) {
          return 0;
        }
      }
      for (int j = i + 1; j <= n; ++j) {
        while (e[j][i]) {
          long long t = e[i][i] / e[j][i];
          for (int k = i; k <= n; ++k) {
            e[i][k] = (e[i][k] - t * e[j][k]) % mod;
            swap(e[i][k], e[j][k]);
          }
          res = -res;
        }
      }
      res = (res * e[i][i]) % mod;
    }
    return (res + mod) % mod;
  }
};
matrix m_qpow(matrix tem, long long x) {
  matrix ret = matrix(tem.row, tem.row);
  ret.getE();
  while (x) {
    if (x & 1) ret = ret * tem;
    x >>= 1;
    tem = tem * tem;
  }
  return ret;
}
int n;
long long m;
struct nod {
  int row;
  long long st, en;
} t[MAX];
struct node {
  int row, kind;
  long long col;
};
bool cmp(node x, node y) {
  if (x.col != y.col)
    return x.col < y.col;
  else if (x.kind != y.kind)
    return x.kind > y.kind;
  else
    return x.row < y.row;
}
node g[MAX << 2];
int ava[10];
int tot;
matrix an(1, 3);
matrix trans(3, 3);
inline void upd() {
  for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 3; j++) {
      if (abs(i - j) > 1 || ava[j])
        trans.e[i][j] = 0;
      else
        trans.e[i][j] = 1;
    }
  }
}
int main() {
  scanf("%d%I64d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d%I64d%I64d", &t[i].row, &t[i].st, &t[i].en);
    g[++tot] = node{t[i].row, 1, t[i].st - 1};
    g[++tot] = node{t[i].row, -1, t[i].en};
  }
  g[++tot] = node{2, 1, m};
  an.e[1][1] = an.e[1][3] = 0;
  an.e[1][2] = 1;
  upd();
  sort(g + 1, g + 1 + tot, cmp);
  long long now = 1;
  for (int i = 1; i <= tot; i++) {
    node tem = g[i];
    an = an * m_qpow(trans, tem.col - now);
    now = tem.col;
    if (tem.kind > 0) {
      ava[tem.row]++;
      upd();
    } else {
      ava[tem.row]--;
      upd();
    }
  }
  if (an.e[1][2] < 0) {
    an.e[1][2] = an.e[1][2] % MOD + MOD;
  }
  printf("%d\n", an.e[1][2]);
}
