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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Runners solver = new Runners();
        solver.solve(1, in, out);
        out.close();
    }

    static class Runners {
        long MOD = (long) (1e9 + 7);
        long inv2 = (long) (5e8 + 4);

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            long M = in.nextLong();
            long[] cur = new long[3];
            cur[1] = 1;
            int[] row = new int[N];
            long[][] it = new long[N][2];
            HashMap<Long, ArrayList<Integer>> map = new HashMap<>();
            for (int i = 1; i <= N; i++) {
                int a = in.nextInt();
                long l = in.nextLong();
                long r = in.nextLong();
                row[i - 1] = a - 1;
                it[i - 1][0] = l;
                it[i - 1][1] = r;
                map.putIfAbsent(l, new ArrayList<>());
                map.putIfAbsent(r, new ArrayList<>());
                map.get(l).add(i);
                map.get(r).add(-i);
            }
            ArrayList<Long> l = new ArrayList<Long>(map.keySet());
            Collections.sort(l);
            ArrayList<long[]> interval = new ArrayList<>();
            long last = 1;
            int[] cnt = new int[3];
            int curMask = 0;
            for (long j : l) {
                int maskb = 0;
                for (int i = 0; i < 3; i++) {
                    if (cnt[i] > 0) {
                        maskb += (1 << i);
                    }
                }
                for (int i : map.get(j)) {
                    if (i > 0) {
                        i--;
                        cnt[row[i]]++;
                    }
                }
                int mask = 0;
                for (int i = 0; i < 3; i++) {
                    if (cnt[i] > 0) {
                        mask += (1 << i);
                    }
                }
                if (last + 1 == j) {
                    interval.add(new long[]{mask, last + 1, j});
                } else {
                    interval.add(new long[]{maskb, last + 1, j - 1});
                    interval.add(new long[]{mask, j, j});
                }
                last = j;
                for (int i : map.get(j)) {
                    if (i < 0) {
                        cnt[row[Math.abs(i) - 1]]--;
                    }
                }

            }
            if (interval.get(interval.size() - 1)[2] != M) {
                interval.add(new long[]{0, interval.get(interval.size() - 1)[2] + 1, M});
            }
            for (long[] i : interval) {
                long diff = i[2] - i[1] + 1;
                if (i[0] == 0) {
                    long[] tempCur = cur.clone();
                    cur[0] = pellPrefix(diff - 1) * (tempCur[0] + tempCur[2]) + getPell(diff) * tempCur[1] + tempCur[0];
                    cur[1] = getPell(diff) * (tempCur[0] + tempCur[2] - tempCur[1]) + getPell(diff + 1) * tempCur[1];
                    cur[2] = pellPrefix(diff - 1) * (tempCur[0] + tempCur[2]) + getPell(diff) * tempCur[1] + tempCur[2];
                } else if (i[0] == 1 || i[0] == 4) {
                    long sum = 0;
                    diff--;
                    long[] tempCur = cur.clone();
                    for (int b = 0; b < 3; b++) {
                        if ((i[0] & (1 << b)) == 0) {
                            if (b == 0) {
                                cur[b] = tempCur[b] + tempCur[b + 1];
                            } else if (b == 1) {
                                cur[b] = tempCur[b] + tempCur[b - 1] + tempCur[b + 1];
                            } else {
                                cur[b] = tempCur[b] + tempCur[b - 1];
                            }
                        } else {
                            cur[b] = 0;
                        }
                    }
                    if (diff > 0) {
                        for (long s : cur) {
                            sum += s;
                        }
                        for (int b = 0; b < 3; b++) {
                            if ((i[0] & (1 << b)) == 0) {
                                cur[b] = MathUtils.binPow(2, diff - 1, MOD) * sum;
                            }
                        }
                    }
                } else if (i[0] == 7) {
                    out.println(0);
                    return;
                } else {
                    long[] tempCur = cur.clone();
                    for (int b = 0; b < 3; b++) {
                        if ((i[0] & (1 << b)) == 0) {
                            if (b == 0) {
                                cur[b] = tempCur[b] + tempCur[b + 1];
                            } else if (b == 1) {
                                cur[b] = tempCur[b] + tempCur[b - 1] + tempCur[b + 1];
                            } else {
                                cur[b] = tempCur[b] + tempCur[b - 1];
                            }
                        } else {
                            cur[b] = 0;
                        }
                    }
                }
                for (int b = 0; b < 3; b++) {
                    cur[b] %= MOD;
                }
            }
            out.println(cur[1]);
        }

        long getPell(long n) {
            long[][] matrix = new long[][]{{2, 1}, {1, 0}};
            Runners.Matrix m = new Runners.Matrix(matrix);
            m = m.pow(n, MOD);
            return m.m[0][1];
        }

        long pellPrefix(long n) {
            long[][] matrix = new long[][]{{1, 1}, {2, 1}};
            Runners.Matrix m = new Runners.Matrix(matrix);
            m = m.pow(n + 1, MOD);
            long H = m.m[0][0];
            return ((H - 1) * inv2) % MOD;
        }

        public static class Matrix {
            public long[][] m;
            int rows;
            int cols;

            public Matrix(long[][] m) {
                rows = m.length;
                cols = m[0].length;
                this.m = m;
            }

            public Matrix(int r, int c) {
                m = new long[r][c];
                rows = r;
                cols = c;
            }

            public Runners.Matrix getIdentity() {
                assert rows == cols : "Matrix is not square, no identity possible";
                long[][] identity = new long[rows][cols];
                for (int i = 0; i < rows; i++) {
                    identity[i][i] = 1;
                }
                return new Runners.Matrix(identity);
            }

            public static Runners.Matrix multiply(Runners.Matrix a, Runners.Matrix b, long mod) {
                //does not change in place
                assert a.cols == b.rows : "Input mismatch, rows do not match columns";
                long[][] newMatrix = new long[a.rows][b.cols];
                for (int i = 0; i < a.rows; i++) {
                    for (int k = 0; k < a.cols; k++) {
                        for (int j = 0; j < b.cols; j++) {
                            newMatrix[i][j] += (a.m[i][k] * b.m[k][j]) % mod;
                            newMatrix[i][j] %= mod;
                        }
                    }
                }
                return new Runners.Matrix(newMatrix);
            }

            public void multiply(Runners.Matrix b, long mod) {
                //changes in place
                assert cols == b.rows : "Input mismatch, rows do not match columns";
                long[][] newMatrix = new long[rows][b.cols];
                for (int i = 0; i < rows; i++) {
                    for (int k = 0; k < cols; k++) {
                        for (int j = 0; j < b.cols; j++) {
                            newMatrix[i][j] += (this.m[i][k] * b.m[k][j]) % mod;
                            newMatrix[i][j] %= mod;
                        }
                    }
                }
                m = newMatrix;
            }

            public Runners.Matrix pow(long n, long mod) {
                //does not change in place
                assert rows == cols : "Matrix is not square";
                Runners.Matrix res = this.getIdentity();
                Runners.Matrix base = new Runners.Matrix(this.m);
                while (n > 0) {
                    if ((n & 1) == 1) {
                        res.multiply(base, mod);
                    }
                    base = Runners.Matrix.multiply(base, base, mod);
                    n = n >> 1;
                }
                return res;
            }

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 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());
        }

    }

    static class MathUtils {
        public static long binPow(long b, long p, long mod) {
            long res = 1;
            while (p > 0) {
                if ((p & 1) == 1) {
                    res *= b;
                    res %= mod;
                }
                b = b * b;
                p >>= 1;
                b %= mod;
            }
            return res;
        }

    }
}

