954_F. Runner's Problem
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
```python
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline


def _mul(A, B, MOD):
    C = [[0] * len(B[0]) for i in range(len(A))]
    for i in range(len(A)):
        for k in range(len(B)):
            for j in range(len(B[0])):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
    return C


def pow_matrix(A, n, MOD):
    B = [[0] * len(A) for i in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1
    while n > 0:
        if n & 1:
            B = _mul(A, B, MOD)
        A = _mul(A, A, MOD)
        n  = n // 2
    return B


def calc(A, vec, MOD):
    n = len(vec)
    res = [0] * n
    for i in range(n):
        for j in range(n):
            res[i] += A[i][j] * vec[j]
            res[i] %= MOD
    return res

n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7


res = [[] for i in range(3)]
for row, l, r in info:
    row -= 1
    l -= 1
    res[row].append((l, r))
for row in range(3):
    res[row].sort(key=itemgetter(1))

blocks = {}
ind_set = set([])
for row in range(3):
    tmp = []
    for l, r in res[row]:
        if not tmp:
            tmp.append((l, r))
            continue
        while tmp:
            if l <= tmp[-1][1]:
                pl, pr = tmp.pop()
                l = min(pl, l)
            else:
                break
        tmp.append((l, r))
    for l, r in tmp:
        if l not in blocks:
            blocks[l] = []
        if r not in blocks:
            blocks[r] = []
        blocks[l].append((row, 1))
        blocks[r].append((row, -1))
        ind_set.add(l)
        ind_set.add(r)

ind_list = sorted(list(ind_set))

dp = [0, 1, 0]
matrix = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]

prv_ind = 0
for ind in ind_list:
    length = (ind - prv_ind - 1)
    tmp_matrix = pow_matrix(matrix, length, MOD)
    dp = calc(tmp_matrix, dp, MOD)
    
    for row, flag in blocks[ind]:
        if flag == 1:
            for i in range(3):
                matrix[row][i] = 0
        else:
            for i in range(3):
                matrix[row][i] = 1
            matrix[0][2] = 0
            matrix[2][0] = 0
    dp = calc(matrix, dp, MOD)
    prv_ind = ind

length = m - prv_ind - 1
tmp_matrix = pow_matrix(matrix, length, MOD)
dp = calc(tmp_matrix, dp, MOD)

print(dp[1] % MOD)
```