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
// upsolve with rainboy
import java.io.*;
import java.util.*;

public class CF954F {
	static final int MD = 1000000007;
	static class V {
		int a;
		long x;
		boolean on;
		V(int a, long x, boolean on) {
			this.a = a; this.x = x; this.on = on;
		}
	}
	static void mult(int[][] aa, int[][] bb, int[][] cc) {
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++) {
				long c = 0;
				for (int k = 0; k < 3; k++)
					c += (long) aa[i][k] * bb[k][j];
				cc[i][j] = (int) (c % MD);
			}
	}
	static void power(int[][] aa, int[][] pp, int[][] tt, long m) {
		if (m == 0) {
			for (int i = 0; i < 3; i++)
				for (int j = 0; j < 3; j++)
					pp[i][j] = i == j ? 1 : 0;
			return;
		}
		if (m % 2 == 0) {
			power(aa, tt, pp, m / 2);
			mult(tt, tt, pp);
		} else {
			power(aa, pp, tt, m / 2);
			mult(pp, pp, tt);
			mult(tt, aa, pp);
		}
	}
	static int[][] pp_ = new int[3][3];
	static int[][] tt_ = new int[3][3];
	static int[] kk_ = new int[3];
	static void update(int[] kk, int[] bb, long m) {
		int[][] aa_ = { { 1, 1, 0 }, { 1, 1, 1 }, { 0, 1, 1 } };
		for (int i = 0; i < 3; i++)
			if (bb[i] != 0)
				for (int j = 0; j < 3; j++)
					aa_[i][j] = 0;
		power(aa_, pp_, tt_, m);
		for (int i = 0; i < 3; i++) {
			long k = 0;
			for (int j = 0; j < 3; j++)
				k += (long) pp_[i][j] * kk[j];
			kk_[i] = (int) (k % MD);
		}
		for (int i = 0; i < 3; i++)
			kk[i] = kk_[i];
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		long m = Long.parseLong(st.nextToken());
		V[] vv = new V[n * 2];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			long l = Long.parseLong(st.nextToken()) - 1;
			long r = Long.parseLong(st.nextToken());
			vv[i * 2 + 0] = new V(a, l, true);
			vv[i * 2 + 1] = new V(a, r, false);
		}
		Arrays.sort(vv, (u, v) -> u.x == v.x ? 0 : u.x < v.x ? -1 : 1);
		int[] kk = new int[3]; kk[1] = 1;
		int[] bb = new int[3];
		long x_ = 1;
		for (int i = 0, j; i < n * 2; i = j) {
			long x = vv[i].x;
			update(kk, bb, x - x_);
			for (j = i; j < n * 2 && vv[j].x == x; j++)
				bb[vv[j].a] += vv[j].on ? 1 : -1;
			x_ = x;
		}
		update(kk, bb, m - x_);
		System.out.println(kk[1]);
	}
}
