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 mod = 1e9 + 7, MAXN = 1e5 + 7;
long long m[8][60][3][3];
long long f[3], g[3];
void init() {
  m[0][0][0][0] = 1;
  m[0][0][0][1] = 1;
  m[0][0][0][2] = 0;
  m[0][0][1][0] = 1;
  m[0][0][1][1] = 1;
  m[0][0][1][2] = 1;
  m[0][0][2][0] = 0;
  m[0][0][2][1] = 1;
  m[0][0][2][2] = 1;
  for (int i = 1; i <= 7; i++)
    for (int j = 0; j <= 2; j++) {
      if (i & (1 << j))
        for (int k = 0; k <= 2; k++) m[i][0][j][k] = 0;
      else
        for (int k = 0; k <= 2; k++) m[i][0][j][k] = m[0][0][j][k];
    }
  for (int i = 1; i < 60; i++)
    for (int j = 0; j <= 7; j++)
      for (int k1 = 0; k1 <= 2; k1++)
        for (int k2 = 0; k2 <= 2; k2++)
          for (int k3 = 0; k3 <= 2; k3++)
            m[j][i][k1][k2] =
                (m[j][i][k1][k2] +
                 m[j][i - 1][k1][k3] * (long long)m[j][i - 1][k3][k2] % mod) %
                mod;
}
long long n, m2;
long long cut[MAXN];
long long cntn, cntn2;
pair<long long, long long> A[MAXN];
pair<long long, pair<long long, long long> > A2[MAXN];
int now3[3], now4;
int main() {
  init();
  cin >> n >> m2;
  for (long long i = 1, i2, i3, i4; i <= n; i++) {
    cin >> i2 >> i3 >> i4;
    A2[++cntn2].first = i3;
    A2[cntn2].second.first = i2 - 1;
    A2[cntn2].second.second = 1;
    A2[++cntn2].first = i4 + 1;
    A2[cntn2].second.first = i2 - 1;
    A2[cntn2].second.second = 0;
  }
  sort(A2 + 1, A2 + 1 + cntn2);
  for (long long i = 1; i <= cntn2; i++) {
    if (A[cntn].first != A2[i].first) A[++cntn].first = A2[i].first;
    if (A2[i].second.second == 0)
      now3[A2[i].second.first]--;
    else
      now3[A2[i].second.first]++;
    now4 = 0;
    if (now3[0]) now4 |= 1;
    if (now3[1]) now4 |= 2;
    if (now3[2]) now4 |= 4;
    A[cntn].second = now4;
  }
  if (A[cntn].first != m2 + 1) {
    A[++cntn].first = m2 + 1;
    A[cntn].second = 0;
  }
  f[1] = 1;
  for (long long i = 1, now = 1, now2 = 0, i2, i3; i <= cntn; i++) {
    if (i == 1)
      i2 = A[i].first - 2;
    else
      i2 = A[i].first - now;
    i3 = 0;
    while (i2) {
      if (i2 & 1) {
        g[0] = g[1] = g[2] = 0;
        for (int k1 = 0; k1 <= 2; k1++) {
          for (int k2 = 0; k2 <= 2; k2++) {
            g[k1] =
                (g[k1] + f[k2] * (long long)m[now2][i3][k1][k2] % mod) % mod;
          }
        }
        f[0] = g[0];
        f[1] = g[1];
        f[2] = g[2];
      }
      i3++;
      i2 >>= 1;
    }
    now2 = A[i].second;
    now = A[i].first;
  }
  cout << f[1] << endl;
}
