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
from __future__ import print_function, division
from collections import OrderedDict
mod = 1000000007

def mat(s, m):
	t = [[0,0,0],[0,0,0],[0,0,0]]
	for i in xrange(3):
		for j in xrange(3):
			t[i][j] = (s[i][0] * m[0][j] + s[i][1] * m[1][j] + s[i][2] * m[2][j]) % mod
	for i in xrange(3):
		s[i] = t[i][:]

def matmul(matrix, v, times):
	if times == 0:
		return
	tmatrix = [[1,1,0],[1,1,1],[0,1,1]]
	for i in xrange(3):
		if v[i] > 0:
			tmatrix[0][i], tmatrix[1][i], tmatrix[2][i] = 0, 0, 0

	ans = [[1,0,0],[0,1,0],[0,0,1]]
	while times > 0:
		if times % 2 == 1:
			# ans = np.matmul(ans, tmatrix)
			mat(ans, tmatrix)
		# tmatrix = np.matmul(tmatrix, tmatrix)
		mat(tmatrix, tmatrix)
		times //= 2

	mat(matrix, ans)
	# matrix = np.matmul(matrix, ans)
def getans():
	run = {}

	n, m = map(int, raw_input().split())

	for i in xrange(n):
		a, l, r = map(int, raw_input().split())
		if not (l-1 in run):
			run[l-1] = [0, 0, 0]
		run[l-1][a-1] += 1

		if not (r in run):
			run[r] = [0, 0, 0]
		run[r][a-1] -= 1

	current = (0, 0, 0)
	run = OrderedDict(sorted(run.items(), key=lambda t: t[0]))

	for k, v in run.iteritems():
		run[k] = (current[0] + v[0], current[1] + v[1], current[2] + v[2])
		current = run[k]

	init_pos = 1
	current = (0, 0, 0)
	matrix = [[1,0,0],[0,1,0],[0,0,1]]
	for k, v in run.iteritems():
		matmul(matrix, current, k - init_pos)
		current = v
		init_pos = k
	matmul(matrix, current, m - init_pos)

	return matrix[1][1]
	
ans = getans()
print("%d" % ans)