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
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.Map.Entry;

public class F {
	

	public static final int ROW = 3;
	public static long[][] matrix(int[] curr_blocked, int[] next_blocked){
		long[][] mat = new long[ROW][ROW];
		
		for(int r = 0; r < ROW; r++){
			if(next_blocked[r] > 0){ continue; }
			
			final int upper = Math.min(r + 1, ROW - 1);
			final int lower = Math.max(r - 1, 0);
			
			for(int c = lower; c <= upper; c++){
				if(curr_blocked[c] > 0){ continue; }
				mat[r][c] = 1; 
			}
		}
		
		return mat;
	}
	
	public static final long MOD = 1000000007;
	public static long[][] mat_mul(long[][] mat, long p){
		if(p == 0){
			return new long[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
		}else if(p == 1){
			return mat;
		}else if(p % 2 == 1){
			return mat_mul(mat, mat_mul(mat, p - 1));
		}else{
			long[][] ret = mat_mul(mat, p / 2);
			return mat_mul(ret, ret);
		}
	}
	
	public static long[][] mat_mul(long[][] mat1, long[][] mat2){
		long[][] ret = new long[ROW][ROW];
		
		for(int from = 0; from < ROW; from++){
			for(int to = 0; to < ROW; to++){
				long sum = 0;
				for(int i = 0; i < ROW; i++){
					sum += mat1[from][i] * mat2[i][to];
					sum %= MOD;
				}
				
				ret[from][to] = sum;
			}
		}
		
		return ret;
	}
	
	public static long[] mat_vec(long[][] mat, long[] vec){
		long[] ret = new long[ROW];
		
		for(int from = 0; from < ROW; from++){
			for(int to = 0; to < ROW; to++){
				ret[from] += mat[from][to] * vec[to];
				ret[from] %= MOD;
			}
		}
		
		return ret;
	}
	
	public static void main(String[] args) {
		try (final Scanner sc = new Scanner(System.in)) {
			final int N = sc.nextInt();
			final long M = sc.nextLong();
			
			TreeMap<Long, ArrayList<Integer>> paint = new TreeMap<Long, ArrayList<Integer>>();
			
			for(int i = 0; i < N; i++){
				final int row = sc.nextInt() - 1;
				final long begin = sc.nextLong();
				final long last  = sc.nextLong();
				final long end   = last + 1;
				
				if(!paint.containsKey(begin)){
					paint.put(begin, new ArrayList<Integer>());
					for(int r = 0; r < ROW; r++){ paint.get(begin).add(0); }
				}
				paint.get(begin).set(row, paint.get(begin).get(row) + 1);
				
				if(!paint.containsKey(end)){
					paint.put(end, new ArrayList<Integer>());
					for(int r = 0; r < ROW; r++){ paint.get(end).add(0); }
				}
				paint.get(end).set(row, paint.get(end).get(row) - 1);
			}
			
			if(!paint.containsKey(M)){
				paint.put(M, new ArrayList<Integer>());
				for(int r = 0; r < ROW; r++){ paint.get(M).add(0); }
			}
			
			//System.out.println(paint);
			
			int[] curr_block = new int[ROW];
			int[] next_block = new int[ROW];
			
			long[] curr_possible = {0, 1, 0};
			
			long time = 1;
			for(final Entry<Long, ArrayList<Integer>> entry : paint.entrySet()){
				final long next_time = entry.getKey();
				
				for(int r = 0; r < ROW; r++){ next_block[r] = curr_block[r]; }
				for(int r = 0; r < ROW; r++){ next_block[r] += entry.getValue().get(r); }
				//System.out.println("PRE : " + " [" + time  + ", " + next_time + ")" + " " + Arrays.toString(curr_block));
				
				final long during_curr_block_time = (next_time - 1) - time;
				//System.out.println(during_curr_block_time + " " + Arrays.deepToString(matrix(curr_block, curr_block)));
				curr_possible = mat_vec(mat_mul(matrix(curr_block, curr_block), during_curr_block_time), curr_possible);
				//System.out.println(Arrays.toString(curr_possible));
				
				//System.out.println(1 + " " + Arrays.deepToString(matrix(curr_block, next_block)));
				curr_possible = mat_vec(mat_mul(matrix(curr_block, next_block), 1), curr_possible);
				
				//System.out.println("POST: " + next_time + " " + Arrays.toString(curr_block) + " " + Arrays.toString(next_block));
				{
					time = next_time;
					int[] tmp = curr_block;
					curr_block = next_block;
					next_block = tmp;
				}
			}
			
			//System.out.println(time);
			System.out.println(curr_possible[1]);
		}
	}
	
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() {
			try {
				while (!hasNext()) {
					tok = new StringTokenizer(br.readLine());
				}
			} catch (IOException e) { /* ignore */
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}

		public void close() {
			try {
				br.close();
			} catch (IOException e) { /* ignore */
			}
		}
	}
}
