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
//package com.company;

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static long TIME_START, TIME_END;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(System.out);
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.in"));
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
//        pw.println("Time used: " + (TIME_END - TIME_START) + ".");
        pw.close();
    }

    public static class Task {
        public class Wall implements Comparable<Wall>{
            int a;
            long x;
            int se;

            public Wall(int a, long l, int r) {
                this.a = a;
                this.x = l;
                this.se = r; // close = 0, open = 1;
            }

            @Override
            public int compareTo(Wall wall) {
                if (x == wall.x) {
                    return Integer.compare(se, wall.se);
                }
                return Long.compare(x, wall.x);
            }
        }

        public class Mat {
            int type;
            long count;

            public Mat(int type, long count) {
                this.type = type;
                this.count = count;
            }
        }
        public final int MOD = 1000000007;

        public int[][] matmul(int[][] a, int[][] b){
            int[][] c = new int[a.length][a.length];
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a.length; j++) {
                    for (int k = 0; k < a.length; k++) {
                        long t = (long)a[i][k] * b[k][j];
                        t %= MOD;
                        c[i][j] += (int)t;
                        if (c[i][j] >= MOD) c[i][j] -= MOD;
                    }
                }
            }
            return c;
        }

        public int[][] powmat(int[][] m, long t) {
            if (t == 0) {
                return new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
            }
            if (t % 2 == 0) {
                return powmat(matmul(arrcpy(m), arrcpy(m)), t >> 1);
            } else {
                return matmul(arrcpy(m), powmat(matmul(arrcpy(m), arrcpy(m)), t >> 1));
            }
        }

        public int[][] arrcpy(int[][] t) {
            int[][] cp = new int[3][3];
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    cp[i][j] = t[i][j];
                }
            }
            return cp;
        }

        public long solve(List<Mat> ttt) {
            long[] start = new long[]{0, 1, 0};
            for (int i = 0; i < ttt.size(); i++) {
                Mat so = ttt.get(i);
                int[][] t = getStart(so.type);
                int[][] res = powmat(t, so.count);
                long[] tmp = new long[3];
                for (int j = 0; j < 3; j++) {
                    for (int k = 0; k < 3; k++) {
                        tmp[j] += res[j][k] * start[k];
                        tmp[j] %= MOD;
                    }
                }
                for (int j = 0; j < 3; j++) {
                    start[j] = tmp[j];
                }
            }
            return start[1];
        }

        public int[][] getStart(int mask) {
            int[][] res = new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
            for (int i = 0; i < 3; i++) {
                if ((mask & (1 << i)) != 0) {
                    for (int j = 0; j < 3; j++) {
                        res[i][j] = 0;
                    }
                }
            }
            return res;
        }

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            int n = sc.nextInt();
            long m = sc.nextLong();
            Wall[] walls = new Wall[n * 2];
            for (int i = 0; i < n; i++) {
                int a = sc.nextInt() - 1;
                long l = sc.nextLong();
                long r = sc.nextLong();
                walls[i << 1] = new Wall(a, l, 1);
                walls[i << 1 | 1] = new Wall(a, r + 1, 0);
            }
            Arrays.sort(walls);
            List<Mat> ttt = new ArrayList<>();
            long curPos = 1;
            int[] cnt = new int[3];
            for (int i = 0; i < walls.length; i++) {
                Wall w = walls[i];
                if (w.se == 1) {
                    if (w.x - curPos > 1){
                        ttt.add(new Mat(getFromCNT(cnt), w.x - curPos - 1));
                        curPos = w.x - 1;
                    }
                    cnt[w.a]++;
                } else {
                    ttt.add(new Mat(getFromCNT(cnt), w.x - curPos - 1));
                    curPos = w.x - 1;
                    cnt[w.a]--;
                }
            }
            ttt.add(new Mat(getFromCNT(cnt), m - curPos));
            pw.println(solve(ttt));
        }
        public int getFromCNT(int[] cnt) {
            int res = 0;
            for (int i = 0; i < cnt.length; i++) {
                if (cnt[i] > 0) {
                    res |= 1 << i;
                }
            }
            return res;
        }
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

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

        public Scanner(FileReader s) throws FileNotFoundException {br = new BufferedReader(s);}

        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {return Integer.parseInt(next());}

        public long nextLong() throws IOException {return Long.parseLong(next());}

        public String nextLine() throws IOException {return br.readLine();}

        public double nextDouble() throws IOException { return Double.parseDouble(next()); }

        public boolean ready() throws IOException {return br.ready();}
    }
}
