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 M = 1e9 + 7;
long long n;
int k;
vector<vector<int> > mul(const vector<vector<int> > &a,
                         const vector<vector<int> > &b) {
  vector<vector<int> > c(3, vector<int>(3));
  for (int i = 0; i < 3; ++i)
    for (int j = 0; j < 3; ++j)
      for (int k = 0; k < 3; ++k)
        c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % M;
  return c;
}
vector<vector<int> > Pow(const vector<vector<int> > &b, long long p) {
  if (p == 1) return b;
  vector<vector<int> > z = Pow(b, p / 2);
  if (p & 1) return mul(mul(z, z), b);
  return mul(z, z);
}
int main() {
  cin >> k >> n;
  vector<long long> mp;
  vector<pair<int, pair<long long, long long> > > bad(k);
  mp.push_back(0);
  mp.push_back(1);
  mp.push_back(2);
  mp.push_back(n);
  for (int i = 0; i < k; ++i) {
    scanf("%d%lld%lld", &bad[i].first, &bad[i].second.first,
          &bad[i].second.second);
    --bad[i].first;
    mp.push_back(bad[i].second.first - 1);
    mp.push_back(bad[i].second.first);
    mp.push_back(bad[i].second.second);
    mp.push_back(bad[i].second.second + 1);
  }
  sort(mp.begin(), mp.end());
  mp.resize(unique(mp.begin(), mp.end()) - mp.begin());
  vector<vector<int> > cs(3, vector<int>(mp.size() + 1));
  for (auto &x : bad) {
    x.second.first =
        lower_bound(mp.begin(), mp.end(), x.second.first) - mp.begin();
    x.second.second =
        lower_bound(mp.begin(), mp.end(), x.second.second) - mp.begin();
    ++cs[x.first][x.second.first];
    --cs[x.first][x.second.second + 1];
  }
  for (int i = 0; i < 3; ++i)
    for (int j = 1; j < cs[i].size(); ++j) cs[i][j] += cs[i][j - 1];
  long long dp[3] = {0, 1, 0};
  for (int i = 2; i < mp.size(); ++i) {
    int l = i;
    int seen = 0;
    if (cs[0][i]) seen |= 1;
    if (cs[1][i]) seen |= 2;
    if (cs[2][i]) seen |= 4;
    int curSeen = seen;
    while (i + 1 < mp.size() && seen == curSeen) {
      ++i;
      curSeen = 0;
      if (cs[0][i]) curSeen |= 1;
      if (cs[1][i]) curSeen |= 2;
      if (cs[2][i]) curSeen |= 4;
    }
    if (seen != curSeen) --i;
    int r = i;
    vector<vector<int> > v(3, vector<int>(3));
    for (int r = 0; r < 3; ++r) {
      for (int r2 = 0; r2 < 3; ++r2)
        if (abs(r - r2) <= 1 && !((seen >> r2) & 1)) ++v[r][r2];
    }
    long long len = mp[r] - mp[l] + 1;
    vector<vector<int> > z = Pow(v, len);
    long long DP[3] = {};
    for (int i = 0; i < 3; ++i)
      for (int j = 0; j < 3; ++j)
        DP[i] = (DP[i] + z[j][i] * (long long)dp[j]) % M;
    for (int i = 0; i < 3; ++i) dp[i] = DP[i];
  }
  printf("%lld\n", dp[1] % M);
  return 0;
}
