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.util.*;
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);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.flush();out.close();
    }
        static class TaskE {
          class pair{
           int type,r;long p;
           pair(int a,long b,int c){type=a;p=b;r=c;}
           public String toString(){return type+" "+p;}
          }
          long mod=(long)(1E9)+7;
          long[] rpe1(long pow,int t,long mat[]){
           long I[][]={{1,0},{0,1}};
           long a[][]={{1,1},{1,1}};
           while(pow!=0){
            if(pow%2!=0){
             I=mul(I,a);
            }
            pow/=2;a=mul(a,a);
           }long b[]=new long[3];
           int add=0;if(t==2)add=1;
           for(int i=0;i<2;i++){
             for(int j=0;j<2;j++)b[i+add]=(b[i+add]+I[i][j]*mat[j+add]%mod)%mod;
           }
           return b;
          }
          long[] rpe2(long pow,long mat[]){
           long a[][]={{1,1,0},{1,1,1},{0,1,1}},I[][]={{1,0,0},{0,1,0},{0,0,1}};
           while(pow!=0){
            if(pow%2!=0){
             I=mul(I,a);
            }pow/=2;a=mul(a,a);
           }
           long b[]=new long[3];
           for(int i=0;i<3;i++){
            for(int j=0;j<3;j++)b[i]=(b[i]+I[i][j]*mat[j]%mod)%mod;
           }return b;
          }
          long[][] mul(long I[][],long a[][]){
           int l=I[0].length;
           long b[][]=new long[l][l];
           for(int i=0;i<l;i++){
            for(int j=0;j<l;j++){
             for(int k=0;k<l;k++)b[i][j]=(b[i][j]+I[i][k]*a[k][j]%mod)%mod;
            }
           }return b;
          }
          long[] get(long a,long b,long c){
           long v[]={a,b,c};
           return v;
          }
          public void solve(int testNumber, InputReader in, PrintWriter out) {
              int n=in.nextInt();long m=in.nextLong();
              ArrayList<pair> al=new ArrayList<>();
              for(int i=0;i<n;i++){
               int row=in.nextInt();long l=in.nextLong(),r=in.nextLong();
               al.add(new pair(0,l,row));al.add(new pair(1,r,row));
              }Collections.sort(al,new Comparator<pair>(){
               public int compare(pair p1,pair p2){
                if(p1.p==p2.p)return p1.type-p2.type;
                return Long.compare(p1.p,p2.p);
               }
              });
              int pv=0,max=al.size();long s=2,e=1;int b[]=new int[4];
              long base[]={0,1,0};
              while(s<=m){e=m;
               for(int j=pv;j<max;){
                pair p=al.get(j);
                if(p.p<s&&p.type==1){
                 ++j;b[p.r]--;continue;
                }
                if(p.p==s){
                 if(p.type==0){
                  b[p.r]++;++j;
                 }else{
                  e=s;pv=j;break;
                 }
                }
                else{
                 if(p.type==0){
                  e=p.p-1;
                 }else{
                  e=p.p;
                 }pv=j;break;
                }
               }//System.out.println(s+" "+e+" "+b[1]+" "+b[2]+" "+b[3]);
               if(b[1]!=0&&b[2]!=0&&b[3]!=0){out.print("0");return;}
               long v1=0,v2=0,v3=0;
               for(int j=0;j<3;j++)v2=(v2+base[j])%mod;
               v1=(v2-base[2]+mod)%mod;v3=(v2-base[0]+mod)%mod;
               if(b[1]!=0&&b[2]!=0&&b[3]==0){
                base=get(0,0,v3);
               }else if(b[1]!=0&&b[2]==0&&b[3]!=0){
                base=get(0,v2,0);
               }else if(b[1]==0&&b[2]!=0&&b[3]!=0){
                base=get(v1,0,0);
               }else if(b[1]!=0&&b[2]==0&&b[3]==0){
                base=get(0,v2,v3);
                base=rpe1(e-s,2,base);
               }else if(b[1]==0&&b[2]==0&&b[3]!=0){
                base=get(v1,v2,0);
                base=rpe1(e-s,1,base);
               }else if(b[1]==0&&b[2]!=0&&b[3]==0){
                base=get(v1,0,v3);
               }else{
                base=rpe2(e-s+1,base);
               }
               //System.out.println();
               //for(int i=0;i<3;i++)System.out.print(base[i]+" ");
               s=e+1;
              }out.print(base[1]);
         }
         /*pair ja[][];long w[];int from[],to[],c[];
             void make(int n,int m,InputReader in){
              ja=new pair[n+1][];w=new long[m];from=new int[m];to=new int[m];c=new int[n+1];
              for(int i=0;i<m;i++){
               int u=in.nextInt(),v=in.nextInt();long wt=in.nextLong();
               c[u]++;c[v]++;from[i]=u;to[i]=v;w[i]=wt;
              }
              for(int i=1;i<=n;i++){
               ja[i]=new pair[c[i]];c[i]=0;
              }
              for(int i=0;i<m;i++){
               ja[from[i]][c[from[i]]++]=new pair(to[i],w[i]);
               ja[to[i]][c[to[i]]++]=new pair(from[i],w[i]);
              }
             }*/
        int[] radixSort(int[] f){ return radixSort(f, f.length); }
	int[] radixSort(int[] f, int n)
	{
		int[] to = new int[n];
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(f[i]&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[f[i]&0xffff]++] = f[i];
			int[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(f[i]>>>16)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[f[i]>>>16]++] = f[i];
			int[] d = f; f = to;to = d;
		}
		return f;
	}
    }
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;
        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}