#pragma GCC optimize ("Ofast") #include using namespace std; #define MD (1000000007U) void *wmem; char memarr[96000000]; template inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } template void sortA_L(int N, T1 a[], void *mem = wmem){ sort(a, a+N); } template void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){ int i; pair *arr; walloc1d(&arr, N, &mem); for(i=(0);i<(N);i++){ arr[i].first = a[i]; arr[i].second = b[i]; } sort(arr, arr+N); for(i=(0);i<(N);i++){ a[i] = arr[i].first; b[i] = arr[i].second; } } struct Modint{ unsigned val; Modint(){ val=0; } Modint(int a){ val = ord(a); } Modint(unsigned a){ val = ord(a); } Modint(long long a){ val = ord(a); } Modint(unsigned long long a){ val = ord(a); } inline unsigned ord(unsigned a){ return a%MD; } inline unsigned ord(int a){ a %= (int)MD; if(a < 0){ a += MD; } return a; } inline unsigned ord(unsigned long long a){ return a%MD; } inline unsigned ord(long long a){ a %= (int)MD; if(a < 0){ a += MD; } return a; } inline unsigned get(){ return val; } inline Modint &operator+=(Modint a){ val += a.val; if(val >= MD){ val -= MD; } return *this; } inline Modint &operator-=(Modint a){ if(val < a.val){ val = val + MD - a.val; } else{ val -= a.val; } return *this; } inline Modint &operator*=(Modint a){ val = ((unsigned long long)val*a.val)%MD; return *this; } inline Modint &operator/=(Modint a){ return *this *= a.inverse(); } inline Modint operator+(Modint a){ return Modint(*this)+=a; } inline Modint operator-(Modint a){ return Modint(*this)-=a; } inline Modint operator*(Modint a){ return Modint(*this)*=a; } inline Modint operator/(Modint a){ return Modint(*this)/=a; } inline Modint operator+(int a){ return Modint(*this)+=Modint(a); } inline Modint operator-(int a){ return Modint(*this)-=Modint(a); } inline Modint operator*(int a){ return Modint(*this)*=Modint(a); } inline Modint operator/(int a){ return Modint(*this)/=Modint(a); } inline Modint operator+(long long a){ return Modint(*this)+=Modint(a); } inline Modint operator-(long long a){ return Modint(*this)-=Modint(a); } inline Modint operator*(long long a){ return Modint(*this)*=Modint(a); } inline Modint operator/(long long a){ return Modint(*this)/=Modint(a); } inline Modint operator-(void){ Modint res; if(val){ res.val=MD-val; } else{ res.val=0; } return res; } inline operator bool(void){ return val!=0; } inline operator int(void){ return get(); } inline operator long long(void){ return get(); } inline Modint inverse(){ int a = val; int b = MD; int u = 1; int v = 0; int t; Modint res; while(b){ t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } if(u < 0){ u += MD; } res.val = u; return res; } inline Modint pw(unsigned long long b){ Modint a(*this); Modint res; res.val = 1; while(b){ if(b&1){ res *= a; } b >>= 1; a *= a; } return res; } inline bool operator==(int a){ return ord(a)==val; } inline bool operator!=(int a){ return ord(a)!=val; } } ; inline Modint operator+(int a, Modint b){ return Modint(a)+=b; } inline Modint operator-(int a, Modint b){ return Modint(a)-=b; } inline Modint operator*(int a, Modint b){ return Modint(a)*=b; } inline Modint operator/(int a, Modint b){ return Modint(a)/=b; } inline Modint operator+(long long a, Modint b){ return Modint(a)+=b; } inline Modint operator-(long long a, Modint b){ return Modint(a)-=b; } inline Modint operator*(long long a, Modint b){ return Modint(a)*=b; } inline Modint operator/(long long a, Modint b){ return Modint(a)/=b; } inline int my_getchar_unlocked(){ static char buf[1048576]; static int s = 1048576; static int e = 1048576; if(s == e && e == 1048576){ e = fread_unlocked(buf, 1, 1048576, stdin); s = 0; } if(s == e){ return EOF; } return buf[s++]; } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = my_getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = my_getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } struct MY_WRITER{ char buf[1048576]; int s; int e; MY_WRITER(){ s = 0; e = 1048576; } ~MY_WRITER(){ if(s){ fwrite_unlocked(buf, 1, s, stdout); } } } ; MY_WRITER MY_WRITER_VAR; void my_putchar_unlocked(int a){ if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){ fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout); MY_WRITER_VAR.s = 0; } MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a; } inline void wt_L(char a){ my_putchar_unlocked(a); } inline void wt_L(int x){ int s=0; int m=0; char f[10]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ my_putchar_unlocked('-'); } while(s--){ my_putchar_unlocked(f[s]+'0'); } } inline void wt_L(Modint x){ int i; i = (int)x; wt_L(i); } template inline T pow_L(T a, S b){ T res = 1; res = 1; for(;;){ if(b&1){ res *= a; } b >>= 1; if(b==0){ break; } a *= a; } return res; } inline double pow_L(double a, double b){ return pow(a,b); } template inline void arrInsert(const int k, int &sz, S a[], const S aval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } a[k] = aval; } template inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } a[k] = aval; b[k] = bval; } template inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } for(i=sz-1;i>k;i--){ c[i] = c[i-1]; } a[k] = aval; b[k] = bval; c[k] = cval; } template inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){ int i; sz++; for(i=sz-1;i>k;i--){ a[i] = a[i-1]; } for(i=sz-1;i>k;i--){ b[i] = b[i-1]; } for(i=sz-1;i>k;i--){ c[i] = c[i-1]; } for(i=sz-1;i>k;i--){ d[i] = d[i-1]; } a[k] = aval; b[k] = bval; c[k] = cval; d[k] = dval; } struct unionFind{ int *d; int N; int M; inline void malloc(const int n){ d = (int*)std::malloc(n*sizeof(int)); M = n; } inline void malloc(const int n, const int fg){ d = (int*)std::malloc(n*sizeof(int)); M = n; if(fg){ init(n); } } inline void free(void){ std::free(d); } inline void walloc(const int n, void **mem=&wmem){ walloc1d(&d, n, mem); M = n; } inline void walloc(const int n, const int fg, void **mem=&wmem){ walloc1d(&d, n, mem); M = n; if(fg){ init(n); } } inline void init(const int n){ int i; N = n; for(i=(0);i<(n);i++){ d[i] = -1; } } inline void init(void){ init(M); } inline int get(int a){ int t = a; int k; while(d[t]>=0){ t=d[t]; } while(d[a]>=0){ k=d[a]; d[a]=t; a=k; } return a; } inline int connect(int a, int b){ if(d[a]>=0){ a=get(a); } if(d[b]>=0){ b=get(b); } if(a==b){ return 0; } if(d[a] < d[b]){ d[a] += d[b]; d[b] = a; } else{ d[b] += d[a]; d[a] = b; } return 1; } inline int operator()(int a){ return get(a); } inline int operator()(int a, int b){ return connect(a,b); } inline int& operator[](const int a){ return d[a]; } inline int size(int a){ a = get(a); return -d[a]; } inline int sizeList(int res[]){ int i; int sz=0; for(i=(0);i<(N);i++){ if(d[i]<0){ res[sz++] = -d[i]; } } return sz; } } ; int N; int M; int L[200000]; int R[200000]; int P[200000]; int sm[200000+1]; int ps; int zs; int ind[200000]; set zero; set pos; int n; int m; int l[200000+1]; int r[200000+1]; int p[200000]; Modint add[200000+1]; Modint dc[200000+1]; Modint solve1(void){ int i; int j; int k; Modint res = 1; sortA_L(m, l, r); k = 0; for(i=(0);i<(m);i++){ if(k && l[i]==l[k-1]){ continue; } arrInsert(k, k, l, l[i], r, r[i]); } m = k; l[m] = n; if(m==0){ return (pow_L((Modint(3)),n)); } res =(pow_L(Modint(3),l[0])); j = k = 0; for(i=(l[0]);i<(n);i++){ res -= dc[i]; res += add[i]; while(l[j] == i){ dc[r[j]+1] += res * ((pow_L(Modint(2),(r[i]-l[i]+1)))); j++; } while(l[k] <= i){ k++; } add[l[k]] += res * ((pow_L(Modint(3),(l[k] - i - 1)))); res *= 2; } return add[n]; } Modint solve2(void){ int i; int cond = 0; unionFind uf; uf.walloc(2*n+2, 1); for(i=(0);i<(m);i++){ if(p[i]==0){ cond += uf(l[i], r[i]+1); cond += uf(l[i]+n+1, r[i]+1+n+1); } else{ cond += uf(l[i], r[i]+1+n+1); cond += uf(l[i]+n+1, r[i]+1); } } for(i=(0);i<(n+1);i++){ if(uf(i)==uf(i+n+1)){ return 0; } } return (pow_L((Modint(2)),(n - cond/2))); } int main(){ int i; wmem = memarr; Modint res; rd(N); rd(M); { int tU__gIr_; for(tU__gIr_=(0);tU__gIr_<(M);tU__gIr_++){ rd(L[tU__gIr_]);L[tU__gIr_] += (-1); rd(R[tU__gIr_]);R[tU__gIr_] += (-1); rd(P[tU__gIr_]); } } for(i=(0);i<(M);i++){ if(P[i]){ sm[L[i]]++; sm[R[i]+1]--; } } for(i=(1);i<(N+1);i++){ sm[i] += sm[i-1]; } for(i=(0);i<(N);i++){ if(sm[i]==0){ zero.insert(i); ind[i] = zs++; } else{ pos.insert(i); ind[i] = ps++; } } for(i=(0);i<(M);i++){ if(P[i] == 0){ set::iterator it1; set::iterator it2; it1 = zero.lower_bound(L[i]); it2 = zero.upper_bound(R[i]); if(it1 == it2){ wt_L(0); wt_L('\n'); return 0; } l[m] = ind[*it1]; if(it2==zero.end()){ r[m] =zs-1; } else{ r[m] =ind[*it2]-1; } m++; } } n = zs; res = solve1(); n = ps; m = 0; for(i=(0);i<(M);i++){ if(P[i]){ set::iterator it1; set::iterator it2; it1 = pos.lower_bound(L[i]); it2 = pos.upper_bound(R[i]); if(it1 == it2){ wt_L(0); wt_L('\n'); return 0; } l[m] = ind[*it1]; if(it2==pos.end()){ r[m] =ps-1; } else{ r[m] =ind[*it2]-1; } if(P[i]==-1){ p[m] =1; } else{ p[m] =0; } m++; } } res *= solve2(); wt_L(res); wt_L('\n'); return 0; } // cLay varsion 20200813-1 [beta] // --- original code --- // int N, M, L[2d5], R[2d5], P[2d5]; // // int sm[2d5+1]; // int ps, zs, ind[2d5]; // set zero, pos; // // int n, m, l[2d5+1], r[2d5+1], p[2d5]; // Modint add[2d5+1], dc[2d5+1]; // // Modint solve1(void){ // int i, j, k; // Modint res = 1; // sortA(m, l, r); // // k = 0; // rep(i,m){ // if(k && l[i]==l[k-1]) continue; // arrInsert(k, k, l, l[i], r, r[i]); // } // m = k; // l[m] = n; // // if(m==0) return (Modint(3)) ** n; // // res = Modint(3) ** l[0]; // j = k = 0; // rep(i,l[0],n){ // res -= dc[i]; // res += add[i]; // while(l[j] == i) dc[r[j]+1] += res * (Modint(2) ** (r[i]-l[i]+1)), j++; // while(l[k] <= i) k++; // add[l[k]] += res * (Modint(3) ** (l[k] - i - 1)); // res *= 2; // } // return add[n]; // } // // Modint solve2(void){ // int cond = 0; // unionFind uf; // uf.walloc(2*n+2, 1); // // rep(i,m){ // if(p[i]==0){ // cond += uf(l[i], r[i]+1); // cond += uf(l[i]+n+1, r[i]+1+n+1); // } else { // cond += uf(l[i], r[i]+1+n+1); // cond += uf(l[i]+n+1, r[i]+1); // } // } // // rep(i,n+1) if(uf(i)==uf(i+n+1)) return 0; // return (Modint(2)) ** (n - cond/2); // } // // { // Modint res; // rd(N,M,(L--,R--,P)(M)); // // rep(i,M) if(P[i]){ // sm[L[i]]++; // sm[R[i]+1]--; // } // rep(i,1,N+1) sm[i] += sm[i-1]; // // rep(i,N){ // if(sm[i]==0){ // zero.insert(i); // ind[i] = zs++; // } else { // pos.insert(i); // ind[i] = ps++; // } // } // // rep(i,M) if(P[i] == 0){ // set::iterator it1, it2; // it1 = zero.lower_bound(L[i]); // it2 = zero.upper_bound(R[i]); // if(it1 == it2) wt(0), return 0; // l[m] = ind[*it1]; // r[m] = if[it2==zero.end(), zs-1, ind[*it2]-1]; // m++; // } // n = zs; // res = solve1(); // // n = ps; // m = 0; // rep(i,M) if(P[i]){ // set::iterator it1, it2; // it1 = pos.lower_bound(L[i]); // it2 = pos.upper_bound(R[i]); // if(it1 == it2) wt(0), return 0; // l[m] = ind[*it1]; // r[m] = if[it2==pos.end(), ps-1, ind[*it2]-1]; // p[m] = if[P[i]==-1, 1, 0]; // m++; // } // res *= solve2(); // // wt(res); // }