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
import sys
input = sys.stdin.buffer.readline

p = 10**9+7
M = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]

def multiply(A, B):
    n = len(A)
    m = len(A[0])
    m2 = len(B[0])
    answer = []
    for i in range(n):
        row = []
        for j in range(m2):
            entry = 0
            for k in range(m):
                entry+=A[i][k]*B[k][j]
                entry = entry % p
            row.append(entry)
        answer.append(row)
    return answer

def identity(n):
    answer = []
    for i in range(n):
        row = []
        for j in range(n):
            if i==j:
                row.append(1)
            else:
                row.append(0)
        answer.append(row)
    return answer

def matrix_power(A, y):
    b = bin(y)[2:]
    n = len(A)
    answer = identity(n)
    start = A
    for i in range(len(b)-1, -1, -1):
        if b[i]=='1':
            answer = multiply(answer, start)
        start = multiply(start, start)
    return answer

def process(A, m):
    n = len(A)
    L = {}
    for i in range(n):
        ai, li, ri = A[i]
        if li not in L:
            L[li] = [[0, 0, 0], [0, 0, 0]]
        if ri+1 not in L:
            L[ri+1] =  [[0, 0, 0], [0, 0, 0]]
        L[li][0][ai-1] = 1
        L[ri+1][1][ai-1] = 1
    L_list = sorted(list(L))
    blocks = [1, 1, 1]
    start = 0
    answer = identity(3)
    for i in range(len(L_list)):
        x = L_list[i]
        I = identity(3)
        for j in range(3):
            I[j][j] = blocks[j]
        M2 = multiply(M, I)
        M2 = matrix_power(M2, x-start-1)
        answer = multiply(answer, M2)
        a, b, c = L[x][0]
        d, e, f = L[x][1]
        if d==1:
            blocks[0] = 1
        if e==1:
            blocks[1] = 1
        if f==1:
            blocks[2] = 1
        if a==1:
            blocks[0] = 0
        if b==1:
            blocks[1] = 0
        if c==1:
            blocks[2] = 0
        start = x
    I = identity(3)
    for j in range(3):
        I[j][j] = blocks[j]
    M2 = multiply(M, I)
    M2 = matrix_power(M2, m-start-1)
    answer = multiply(answer, M2)
    return answer[0][0]
        
n, m = [int(x) for x in input().split()]
A = []
for i in range(m):
    a, l, r = [int(x) for x in input().split()]
    A.append([a, l, r])
print(process(A, m))    