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;
typedef struct p {
  long long a, l, r;
} P;
long long n, m;
vector<vector<long long> > I(3, vector<long long>(3));
vector<long long> b;
vector<P> v;
bool block[3][20005];
vector<vector<long long> > mul(vector<vector<long long> > A,
                               vector<vector<long long> > B) {
  vector<vector<long long> > res(3, vector<long long>(3));
  for (int i = 0; i < 3; i++) {
    for (int k = 0; k < 3; k++) {
      for (int j = 0; j < 3; j++) {
        res[i][j] = (res[i][j] + A[i][k] * B[k][j]) % 1000000007;
      }
    }
  }
  return res;
}
vector<vector<long long> > power(vector<vector<long long> > A, long long k) {
  vector<vector<long long> > res = I;
  while (k) {
    if (k & 1) res = mul(res, A);
    A = mul(A, A);
    k >>= 1;
  }
  return res;
}
vector<vector<long long> > T000(3, vector<long long>(3));
vector<vector<long long> > T100(3, vector<long long>(3));
vector<vector<long long> > T010(3, vector<long long>(3));
vector<vector<long long> > T001(3, vector<long long>(3));
vector<vector<long long> > T110(3, vector<long long>(3));
vector<vector<long long> > T011(3, vector<long long>(3));
vector<vector<long long> > T101(3, vector<long long>(3));
vector<vector<long long> > T111(3, vector<long long>(3));
int main() {
  for (int i = 0; i < 3; i++) I[i][i] = 1;
  T100[0][0] = 1;
  T100[0][1] = 1;
  T100[0][2] = 0;
  T100[1][0] = 0;
  T100[1][1] = 0;
  T100[1][2] = 0;
  T100[2][0] = 0;
  T100[2][1] = 0;
  T100[2][2] = 0;
  T010[0][0] = 0;
  T010[0][1] = 0;
  T010[0][2] = 0;
  T010[1][0] = 1;
  T010[1][1] = 1;
  T010[1][2] = 1;
  T010[2][0] = 0;
  T010[2][1] = 0;
  T010[2][2] = 0;
  T001[0][0] = 0;
  T001[0][1] = 0;
  T001[0][2] = 0;
  T001[1][0] = 0;
  T001[1][1] = 0;
  T001[1][2] = 0;
  T001[2][0] = 0;
  T001[2][1] = 1;
  T001[2][2] = 1;
  T110[0][0] = 1;
  T110[0][1] = 1;
  T110[0][2] = 0;
  T110[1][0] = 1;
  T110[1][1] = 1;
  T110[1][2] = 1;
  T110[2][0] = 0;
  T110[2][1] = 0;
  T110[2][2] = 0;
  T101[0][0] = 1;
  T101[0][1] = 1;
  T101[0][2] = 0;
  T101[1][0] = 0;
  T101[1][1] = 0;
  T101[1][2] = 0;
  T101[2][0] = 0;
  T101[2][1] = 1;
  T101[2][2] = 1;
  T011[0][0] = 0;
  T011[0][1] = 0;
  T011[0][2] = 0;
  T011[1][0] = 1;
  T011[1][1] = 1;
  T011[1][2] = 1;
  T011[2][0] = 0;
  T011[2][1] = 1;
  T011[2][2] = 1;
  T111[0][0] = 1;
  T111[0][1] = 1;
  T111[0][2] = 0;
  T111[1][0] = 1;
  T111[1][1] = 1;
  T111[1][2] = 1;
  T111[2][0] = 0;
  T111[2][1] = 1;
  T111[2][2] = 1;
  scanf("%lld%lld", &n, &m);
  for (int i = 0; i < n; i++) {
    long long a, l, r;
    scanf("%lld%lld%lld", &a, &l, &r);
    a--;
    r++;
    v.push_back(p{a, l, r});
    b.push_back(l);
    b.push_back(r);
  }
  b.push_back(2);
  b.push_back(m);
  sort(b.begin(), b.end());
  b.erase(unique(b.begin(), b.end()), b.end());
  for (int i = 0; i < n; i++) {
    v[i].l = find(b.begin(), b.end(), v[i].l) - b.begin();
    v[i].r = find(b.begin(), b.end(), v[i].r) - b.begin();
    for (int j = v[i].l; j < v[i].r; j++) block[v[i].a][j] = 1;
  }
  vector<vector<long long> > ans(3, vector<long long>(3));
  ans = T111;
  for (int i = b.size() - 2; i >= 0; i--) {
    bool x = block[0][i], y = block[1][i], z = block[2][i];
    if (x == 0 && y == 0 && z == 0)
      ans = mul(ans, power(T111, b[i + 1] - b[i]));
    else if (x == 1 && y == 0 && z == 0)
      ans = mul(ans, power(T011, b[i + 1] - b[i]));
    else if (x == 0 && y == 1 && z == 0)
      ans = mul(ans, power(T101, b[i + 1] - b[i]));
    else if (x == 0 && y == 0 && z == 1)
      ans = mul(ans, power(T110, b[i + 1] - b[i]));
    else if (x == 1 && y == 1 && z == 0)
      ans = mul(ans, power(T001, b[i + 1] - b[i]));
    else if (x == 0 && y == 1 && z == 1)
      ans = mul(ans, power(T100, b[i + 1] - b[i]));
    else if (x == 1 && y == 0 && z == 1)
      ans = mul(ans, power(T010, b[i + 1] - b[i]));
    else if (x == 1 && y == 1 && z == 1)
      ans = mul(ans, power(T000, b[i + 1] - b[i]));
  }
  printf("%lld", ans[1][1]);
  return 0;
}
