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.*;
import java.text.*;
import java.util.*;
import java.math.*;
public class template {
	public static final int MOD = 1_000_000_007;
	public static void main(String[] args) throws Exception {
		new template().run();
	}
	public void run() throws Exception {
		FastScanner f = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		int n = f.nextInt();
		long m = f.nextLong();
		PriorityQueue<Pair> pq1 = new PriorityQueue<Pair>();
		PriorityQueue<Pair> pq2 = new PriorityQueue<Pair>();
		for(int i = 0; i < n; i++)
			pq1.add(new Pair(f.nextInt()-1, f.nextLong(), f.nextLong()+1));
		long curm = 1;
		long[][] cur = {{0,1,0}};
		long[][] mat = {{1,1,0},{1,1,1},{0,1,1}};
		long[][] defaul = {{1,1,0},{1,1,1},{0,1,1}};
		int[] cnts = new int[3];
		while(!pq1.isEmpty() || !pq2.isEmpty()) {
			if(pq1.isEmpty() || !pq2.isEmpty() && pq2.peek().a < pq1.peek().a) {
				//remove seg
				Pair p = pq2.poll();
				cur = mult(cur,pow(mat,curm-p.a));
				cnts[p.r]--;
				if(cnts[p.r] == 0)
					for(int i = 0; i < 3; i++)
						mat[p.r][i] = defaul[p.r][i];
				curm = p.a;
			} else {
				//add seg
				Pair p = pq1.poll();
				cur = mult(cur,pow(mat,curm-p.a));
				pq2.add(p.getComp());
				if(cnts[p.r] == 0)
					for(int i = 0; i < 3; i++)
						mat[p.r][i] = 0;
				cnts[p.r]++;
				curm = p.a;
			}
			//System.out.println(Arrays.toString(cur[0]));
		}
		cur = mult(cur,pow(mat,m-curm));
		System.out.println(cur[0][1]);
		out.flush();
	}
	public long[][] pow(long[][] mat, long e) {
		if(e == 0) return new long[][] {{1,0,0},{0,1,0},{0,0,1}};
		long[][] m = pow(mat,e/2);
		m = mult(m,m);
		if((e & 1) == 1) return mult(m,mat);
		return m;
	}
	public long[][] mult(long[][] mat1, long[][] mat2) {
		long[][] ans = new long[mat1.length][mat2[0].length];
		for(int i = 0; i < mat1.length; i++) {
			for(int j = 0; j < mat2[0].length; j++) {
				for(int k = 0; k < mat1[0].length; k++)
					ans[i][j] = (ans[i][j] + mat1[i][k]*mat2[k][j]% MOD) % MOD;
			}
		}
		return ans;
	}
	class Pair implements Comparable<Pair> {
		long a, b;
		int r;
		public Pair(int r, long a, long b) {
			this.a = a;
			this.b = b;
			this.r = r;
		}
		public int compareTo(Pair p) {
			if(a != p.a) return Long.compare(a, p.a);
			else return Long.compare(b, p.b);
		}
		public Pair getComp() {
			return new Pair(r,b,a);
		}
	}
    static class FastScanner {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public FastScanner() {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
        	return Long.parseLong(next());
        }
        public double nextDouble() {
        	return Double.parseDouble(next());
        }
        public String nextLine() {
        	try {
        		return reader.readLine();
        	} catch(IOException e) {
        		throw new RuntimeException(e);
        	}
        }


    }
}