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

public class Main{
    final long IINF = (long)1e12, mod = (long)1e9+7;
    DecimalFormat df = new DecimalFormat("0.0000000000");
    final double EPS = 1e-8;
    FastReader in;
    PrintWriter out;
    boolean multipleTC = false;
    public static void main(String[] args) throws Exception{
        new Thread(null, new Runnable() {
            public void run(){
                try{new Main().run();}catch(Exception e){e.printStackTrace();}
            }
        }, "1", 1 << 26).start();
    }
    
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        for(int i = 1, t = (multipleTC)?ni():1; i<=t; i++)solve(i);
        out.flush();    
        out.close();
    }
    
    void solve(int tc) throws Exception{
        long[][][] a = new long[8][3][3];
        for(int i = 0; i< 8; i++)a[i] = make(i);
        int n = ni();
        long m = nl();
        long[][] tmp = new long[n][3];
        for(int i = 0; i< n; i++)tmp[i] = new long[]{ni()-1, nl(), nl()};
        Arrays.sort(tmp, new Comparator<long[]>(){
            public int compare(long[] l1, long[] l2){
                return Long.compare(l1[1], l2[1]);
            }
        });
        long[][] seg = new long[3*n][3];
        TreeSet<Long> map[] = new TreeSet[3];
        for(int i = 0; i< 3; i++)map[i] = new TreeSet<>();
        long pos = 1;
        int ind = 0;
        for(int j = 0; pos<=m; ){
            long next = m;
            while(j<n && tmp[j][1]==pos){
                map[(int)tmp[j][0]].add(tmp[j][2]);
                j++;
            }
            if(j<n)next = Math.min(next, tmp[j][1]-1);
            int cur = 0;
            for(int i= 0; i< 3; i++){
                while(!map[i].isEmpty() && map[i].first()<pos)map[i].pollFirst();
                if(map[i].size()>0){
                    next = Math.min(next,map[i].first());
                    cur |= 1<<i;
                }
            }
            seg[ind++] = new long[]{7^cur, pos,next};
            pos = next+1;
        }
        seg = Arrays.copyOfRange(seg, 0, ind);
        long[][] ans = new long[][]{
            {0},{1},{0}
        };
        
        for(int i = 0; i< ind; i++){
            long steps = seg[i][2]-seg[i][1];
            if(steps>0)ans = multiply(pow(a[(int)seg[i][0]], steps), ans);
            if(i<ind-1)ans = step(ans, (int)seg[i+1][0]);
        }
        pn(ans[1][0]);
    }
    
    void print(long[][] l){
        for(long[] l1:l){
            for(long l2:l1)p(l2+" ");
            pn("");
        }
    }
    
    long[][] step(long[][] ans, int cur){
        long[][] o = new long[3][1];
        if((cur&1)==1)o[0][0] = (ans[0][0]+ans[1][0])%mod;
        if(((cur>>1)&1)==1)o[1][0] = (ans[0][0]+ans[1][0]+ans[2][0])%mod;
        if(((cur>>2)&1)==1)o[2][0] = (ans[1][0]+ans[2][0])%mod;
        return o;
    }
    
    long[][] make(int cur){
        long[][] o = new long[3][3];
        for(int i = 0; i< 3; i++)for(int j = 0; j< 3; j++)if(((cur>>i)&1)==1 && ((cur>>j)&1)==1)o[i][j] = A[i][j];
        return o;
    }
    
    long[][] A = new long[][]{
        {1,1,0}, {1,1,1}, {0,1,1}
    };
    
    long[][] pow(long[][] m, long p) throws Exception{
        long[][] o = new long[m.length][m.length], t = new long[m.length][m.length];
        for(int i = 0; i< m.length; i++)for(int j = 0; j< m.length; j++)t[i][j] = m[i][j];
        for(int i = 0; i< m.length; i++)o[i][i] = 1;
        while(p>0){
            if(p%2==1)o = multiply(o,t);
            t = multiply(t,t);
            p>>=1;
        }
        return o;
    }
    
    long[][] multiply(long[][] a, long[][] b) throws Exception{
        if(a[0].length!=b.length)throw new Exception();
        long[][] c = new long[a.length][b[0].length];
        for(int i = 0; i< a.length; i++){
            for(int j = 0; j< b[0].length; j++){
                for(int k = 0; k< b.length; k++)c[i][j]=add(c[i][j], mul(a[i][k],b[k][j]));
            }
        }
        return c;
    }
    
    long mul(long a,long b){
        if(a>=mod)a%=mod;
        if(b>=mod)b%=mod;
        a*=b;
        if(a>=mod)a%=mod;
        return a;
    }
    
    long add(long a, long b){
        if(a>=mod)a%=mod;
        if(b>=mod)b%=mod;
        a+=b;
        if(a>=mod)a-=mod;
        return a;
    }
    
    int[] reverse(int[] a){
        int[] o = new int[a.length];
        for(int i = 0; i< a.length; i++)o[i] = a[a.length-i-1];
        return o;   
    }

    int[] sort(int[] a){
        if(a.length==1)return a;
        int mid = a.length/2;
        int[] b = sort(Arrays.copyOfRange(a,0,mid)), c = sort(Arrays.copyOfRange(a,mid,a.length));
        for(int i = 0, j = 0, k = 0; i< a.length; i++){
            if(j<b.length && k<c.length){
                if(b[j]<c[k])a[i] = b[j++];
                else a[i] = c[k++];
            }else if(j<b.length)a[i] = b[j++];
            else a[i] = c[k++];
        }
        return a;
    }

    long[] sort(long[] a){
        if(a.length==1)return a;
        int mid = a.length/2;
        long[] b = sort(Arrays.copyOfRange(a,0,mid)), c = sort(Arrays.copyOfRange(a,mid,a.length));
        for(int i = 0, j = 0, k = 0; i< a.length; i++){
            if(j<b.length && k<c.length){
                if(b[j]<c[k])a[i] = b[j++];
                else a[i] = c[k++];
            }else if(j<b.length)a[i] = b[j++];
            else a[i] = c[k++];
        }
        return a;
    }

    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bitcount(long n){return (n==0)?0:(1+bitcount(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n(){return in.next();}
    int ni() throws Exception{return Integer.parseInt(in.next());}
    long nl() throws Exception{return Long.parseLong(in.next());}
    double nd() throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }
 
        String next(){
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}       