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.util.*;
import java.io.*;

public class Runner {
		static int a[] = new int [10010];
		static long l[] = new long [10010];
		static long r[] = new long [10010];
		static int n;
		static final int mod = 1000000000 + 7;
		static class Matrix {
			long [][] mat;
			int n, m;
			Matrix (int n, int m) {
				this.n = n;
				this.m = m;
				mat = new long [n][m];
				for(int i = 0; i < n; i++) {
					for(int j = 0; j < m; j++) {
						mat[i][j] = 0;
					}
				}
			}
			void print() {
				for(int i = 0; i < n; i++) {
					for(int j = 0; j < m; j++) {
						System.out.printf("%d ", mat[i][j]);
					}
					System.out.println();
				}
				System.out.println();
			}
		}
		static Matrix multiply(Matrix a, Matrix b) {
			Matrix ans = new Matrix (a.n, b.m);
			for(int i = 0; i < ans.n; i++) {
				for(int j = 0; j < ans.m; j++) {
					for(int k = 0; k < a.m; k++) {
						ans.mat[i][j] += a.mat[i][k] * b.mat[k][j];
						ans.mat[i][j] %= mod;
					}
				}
			}
			return ans;
		}
		static Matrix modpow(Matrix x, long p) {
			if(p == 0) {
				Matrix id = new Matrix (x.n, x.m);
				for(int i = 0; i < x.n; i++) id.mat[i][i] = 1;
				return id;
			}
			if(p % 2 == 1) return multiply(modpow(x, p - 1), x);
			Matrix m = modpow(x, p >> 1);
			return multiply(m, m);  
		}
		
		static int get(int x, long y) {
			for(int i = 1; i <= n; i++) {
				if(a[i] == x && l[i] <= y && y <= r[i]) {
					return 1;
				}
			}
			return 0;
		}
		
    public static void main(String [] args) {
      Reader in = new Reader ();
      Writer out = new Writer ();
      n = in.nextInt();
      long m = in.nextLong();
      
      ArrayList <Pair> arr = new ArrayList <> ();
      for(int i = 1; i <= n; i++) {
				a[i] = in.nextInt() - 1;
				l[i] = in.nextLong();
				r[i] = in.nextLong();
				arr.add(new Pair(l[i], -1));
				arr.add(new Pair(r[i], 1));
			}
			arr.add(new Pair(1, -1));
			arr.add(new Pair(m, 1));
			Collections.sort(arr, new Pair());
			
			ArrayList <Pair> block = new ArrayList <> ();
			for(int i = 0; i < arr.size() - 1; i++) {
				if(arr.get(i).second == -1) {
					if(arr.get(i + 1).second == -1) block.add(new Pair(arr.get(i).first, arr.get(i + 1).first - 1));
					else block.add(new Pair(arr.get(i).first, arr.get(i + 1).first));
				} else {
					if(arr.get(i + 1).second == -1) block.add(new Pair(arr.get(i).first + 1, arr.get(i + 1).first - 1));
					else block.add(new Pair(arr.get(i).first + 1, arr.get(i + 1).first));
				}
			}
			Matrix row = new Matrix (3, 1);
			row.mat[0][0] = 0;
			row.mat[1][0] = 1;
			row.mat[2][0] = 0;
			int last = 0;
			
			for(Pair i : block) {
				if(i.first > i.second) continue;
				
				// System.out.println(i.first + " " + i.second);
				
				long [] shit = new long [3];
				shit[0] = shit[1] = shit[2] = 0;
				
				if(i.first > 1) {
					if(((last >> 0) & 1) == 0) {
						shit[0] += row.mat[0][0];
						shit[1] += row.mat[0][0];
					}
					if(((last >> 1) & 1) == 0) {
						shit[0] += row.mat[1][0];
						shit[1] += row.mat[1][0];
						shit[2] += row.mat[1][0];
					}
					if(((last >> 2) & 1) == 0) {
						shit[2] += row.mat[2][0];
						shit[1] += row.mat[2][0];
					}
					for(int j = 0; j < 3; j++) {
						row.mat[j][0] = shit[j] % mod;
					}
				}
				
				last = 0;
				boolean bad[] = new boolean [3];
				for(int j = 0; j < 3; j++) {
					if(get(j, i.first) == 1) {
						row.mat[j][0] = 0;
						bad[j] = true;
						last |= 1 << j;
					} else {
						bad[j] = false;
					}
				}
				// row.print();
				
				long shift = i.second - i.first;
				Matrix fuck = new Matrix (3, 3);
				for(int j = 0; j < 3; j++) {
					for(int k = 0; k < 3; k++) {
						fuck.mat[j][k] = 1;
					}
				}
				fuck.mat[0][2] = 0;
				fuck.mat[2][0] = 0;
				for(int k = 0; k < 3; k++) {
					if(!bad[k]) continue;
					for(int j = 0; j < 3; j++) {
						fuck.mat[k][j] = 0;
						fuck.mat[j][k] = 0;
					}
				}
				// fuck.print();				
				row = multiply(modpow(fuck, shift), row);
			}
			// row.print();
			System.out.println(row.mat[1][0]);
    }
    static class Reader {
        private StringTokenizer a;
        private BufferedReader b;
        Reader () {
            a = null;
            b = new BufferedReader (new InputStreamReader (System.in));
        }
        public String next () {
            while(a == null || !a.hasMoreTokens()) {
                try {
                    a = new StringTokenizer (b.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return a.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(this.next());
        }
        public long nextLong () {
            return Long.parseLong(this.next());
        }
        public double nextDouble () {
            return Double.parseDouble(this.next());
        }
        public String nextLine() {
            try {
                return b.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return "";
        }
    }
    static class Writer {
        private PrintWriter a;
        private StringBuffer b;
        Writer () {
            a = new PrintWriter (System.out);
            b = new StringBuffer ("");
        }
        public void write (Object s) {
            b.append(s);
        }
        public void writeln(Object s) {
            b.append(s).append('\n');
        }
        public void flush () {
            a.print(b);
            a.flush();
            a.close();
        }
    }
    static class Pair implements Comparator <Pair> {
        long first;
        long second;
        Pair  (long a, long b) {
            this.first = a;
            this.second = b;
        }
        Pair (Pair a) {
            this.first = a.first;
            this.second = a.second;
        } 
        Pair () {}
        public String toString () {
            return "[" + first + ", " + second + "]";
        }
        long diff(long val) {
					if(val == 0) return 0;
					else return val / Math.abs(val);
				}
        public int compare (Pair a, Pair b) {
            if(a.first == b.first) {
                return (int) diff(a.second - b.second);
            } else {
                return (int) diff(a.first - b.first);
            }
        }
    } 
}
