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;
inline long long read() {
  long long l = 0, f = 1;
  char a = getchar();
  for (; a < '0' || a > '9'; a = getchar())
    if (a == '-') f = -1;
  for (; a >= '0' && a <= '9'; a = getchar()) l = l * 10 + a - 48;
  return l * f;
}
const int N = 10005, M = 3;
const int p = 1e9 + 7;
struct Seg {
  long long p, a, f;
} a[N << 1];
struct Matrix {
  int c[M][M];
  Matrix() { memset(c, 0, sizeof(c)); }
  int *operator[](int i) { return c[i]; }
  const int *operator[](int i) const { return c[i]; }
} ans;
long long n, m, num, now[M];
bool operator<(const Seg &a, const Seg &b) { return a.p < b.p; }
Matrix operator*(const Matrix &A, const Matrix &B) {
  Matrix R;
  for (int i = 0; i < M; i++)
    for (int k = 0; k < M; k++)
      for (int j = 0; j < M; j++)
        R[i][j] = (int)((R[i][j] + (long long)A[i][k] * B[k][j]) % p);
  return R;
}
Matrix build() {
  Matrix R;
  if (!now[0]) R[0][0] = R[1][0] = 1;
  if (!now[1]) R[0][1] = R[1][1] = R[2][1] = 1;
  if (!now[2]) R[1][2] = R[2][2] = 1;
  return R;
}
void ksm(Matrix &a, Matrix c, long long b) {
  for (; b; b >>= 1) {
    if (b & 1) a = a * c;
    c = c * c;
  }
}
int main(int argc, char const *argv[]) {
  n = read(), m = read();
  a[++num] = {2, 0, 0};
  for (int i = 1; i <= n; ++i) {
    long long ai = read(), l = read(), r = read();
    a[++num] = {l, ai - 1, 1};
    a[++num] = {r + 1, ai - 1, -1};
  }
  sort(a + 1, a + 1 + num);
  a[++num] = {m + 1, 0, 0};
  for (int i = 0; i < M; ++i) ans[i][i] = 1;
  for (int i = 1; i < num; ++i) {
    now[a[i].a] += a[i].f;
    ksm(ans, build(), a[i + 1].p - a[i].p);
  }
  printf("%d\n", ans[1][1]);
  return 0;
}
