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* &gt; 1, -  (*i*, *j* + 1), or -  (*i* + 1, *j* + 1) — only if *i* &lt; 3. 
However, there are *n* obstacles blocking your path. *k*-th obstacle is denoted by three integers *a*<sub class="lower-index">*k*</sub>, *l*<sub class="lower-index">*k*</sub> and *r*<sub class="lower-index">*k*</sub>, and it forbids entering any cell (*a*<sub class="lower-index">*k*</sub>, *j*) such that *l*<sub class="lower-index">*k*</sub> ≤ *j* ≤ *r*<sub class="lower-index">*k*</sub>.

You have to calculate the number of different paths from (2, 1) to (2, *m*), and print it modulo 10<sup class="upper-index">9</sup> + 7.
The first line contains two integers *n* and *m* (1 ≤ *n* ≤ 10<sup class="upper-index">4</sup>, 3 ≤ *m* ≤ 10<sup class="upper-index">18</sup>) — the number of obstacles and the number of columns in the matrix, respectively.

Then *n* lines follow, each containing three integers *a*<sub class="lower-index">*k*</sub>, *l*<sub class="lower-index">*k*</sub> and *r*<sub class="lower-index">*k*</sub> (1 ≤ *a*<sub class="lower-index">*k*</sub> ≤ 3, 2 ≤ *l*<sub class="lower-index">*k*</sub> ≤ *r*<sub class="lower-index">*k*</sub> ≤ *m* - 1) denoting an obstacle blocking every cell (*a*<sub class="lower-index">*k*</sub>, *j*) such that *l*<sub class="lower-index">*k*</sub> ≤ *j* ≤ *r*<sub class="lower-index">*k*</sub>. Some cells may be blocked by multiple obstacles.
none
2 5
1 3 4
2 2 3
2
50 100
3 24 49
2 10 12
1 87 92
2 19 60
2 53 79
3 65 82
3 10 46
1 46 86
2 55 84
1 50 53
3 80 81
3 66 70
2 35 52
1 63 69
2 65 87
3 68 75
1 33 42
1 56 90
3 73 93
2 20 26
2 42 80
2 83 87
3 99 99
1 14 79
2 94 97
1 66 85
1 7 73
1 50 50
2 16 40
2 76 94
1 71 98
1 99 99
1 61 87
3 98 98
2 11 41
3 67 78
1 31 58
3 81 85
1 81 94
3 41 83
3 46 65
1 94 94
3 31 38
1 19 35
3 50 54
3 85 90
3 47 63
3 62 87
1 18 75
1 30 41
0
50 100
1 71 96
2 34 52
2 16 95
1 54 55
1 65 85
1 76 92
2 19 91
1 26 43
2 83 95
2 70 88
2 67 88
1 9 75
2 4 50
2 9 11
1 77 92
1 28 58
1 23 72
1 24 75
2 12 50
1 54 55
2 45 93
1 88 93
2 98 99
1 40 58
2 40 42
1 16 61
2 94 94
1 82 86
2 81 85
2 46 46
2 88 97
2 6 86
1 30 86
2 87 96
1 44 50
2 43 88
1 29 98
1 39 76
1 78 94
1 6 69
2 92 95
1 40 68
1 97 99
1 85 85
1 69 74
1 23 51
1 34 66
2 70 98
2 94 97
1 54 73
5
# A*B
def mat_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

#A**n
def mat_pow(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 == 1:
            B = mat_mul(A, B, mod)
        A = mat_mul(A, A, mod)
        n = n>>1
    return B

n, m = map(int, input().split())
mod = 10**9+7
from collections import defaultdict
E = defaultdict(lambda: [])
for i in range(n):
    a, l, r = map(int, input().split())
    a, l, r = a-1, l-1, r-1
    E[l].append((1, a))
    E[r+1].append((-1, a))

E = list(E.items())
E.sort(key=lambda x: x[0])
#print(E)
block = [0]*3
pos = 0
M = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
X = [0, 1, 0]
for x, L in E:
    A = mat_pow(M, x-pos, mod)
    nX = [0, 0, 0]
    for i in range(3):
        for j in range(3):
            nX[i] += X[j]*A[i][j]
            nX[i] %= mod
    X = nX
    for t, a in L:
        if t == 1:
            block[a] += 1
        else:
            block[a] -= 1
    if block[0] > 0:
        M[0] = [0, 0, 0]
    else:
        M[0] = [1, 1, 0]
    if block[1] > 0:
        M[1] = [0, 0, 0]
    else:
        M[1] = [1, 1, 1]
    if block[2] > 0:
        M[2] = [0, 0, 0]
    else:
        M[2] = [0, 1, 1]
    pos = x
A = mat_pow(M, m-1-pos, mod)
nX = [0, 0, 0]
for i in range(3):
    for j in range(3):
        nX[i] += X[j]*A[i][j]
        nX[i] %= mod
X = nX
print(X[1]%mod)
