//#include #include "bits/stdc++.h" using namespace std; typedef long long ll; /* #include "boost/multiprecision/cpp_int.hpp" #include "boost/multiprecision/cpp_dec_float.hpp" namespace mp = boost::multiprecision; typedef mp::cpp_int LL; typedef mp::number> DD;// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする) */ typedef long double dd; #define i_7 (ll)(1E9+7) //#define i_7 998244353 #define i_5 i_7-2 ll mod(ll a){ ll c=a%i_7; if(c>=0)return c; return c+i_7; } typedef pair l_l; typedef pair d_d; ll inf=(ll)1E16; #define rep(i,l,r) for(ll i=l;i<=r;i++) #define rrep(i,r,l) for(ll i=r;i>=l;i--) #define pb push_back ll max(ll a,ll b){if(ab)return b;else return a;} void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]); void Min(ll &pos,ll val){pos=min(pos,val);} void Add(ll &pos,ll val){pos=mod(pos+val);} dd EPS=1E-12; #define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define fi first #define se second #define endl "\n" //インタラクティブで消す!!!!!!!!!!!!!!!!!!!!! #define SORT(v) sort(v.begin(),v.end()) #define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end()) #define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin()) #define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin()) template inline bool chmax(T &a, S b) { if(a < b) { a = b; return true; } return false; } template inline bool chmin(T &a, S b) { if(a > b) { a = b; return true; } return false; } void mod_print(ll k){ ll P=50000; rep(y,1,P){ ll x=mod(y*k); if(abs(x)<=P||x+P>=i_7){ if(x+P>=i_7){ x-=i_7; } cout< vl; ////////////////////////// template struct Segtree { ll n, n_org; vector dat; Func_mv merge_values; //dataとdataの演算 T te; //dataの単位元かつ初期値 Segtree(){} Segtree(ll n_org, Func_mv merge_values, T te): n_org(n_org), merge_values(merge_values), te(te){ n = 1; while(n < n_org) n <<= 1; dat.resize(2*n-1, te); } void build(vector& A){ for(ll k=0; k=0; k--) dat[k] = merge_values(dat[2*k+1], dat[2*k+2]); } void update(ll k, T x){ //位置kの要素を更新 k+=n-1; dat[k]=x; while(k>0){ k=(k-1)/2; dat[k]=merge_values(dat[2*k+1],dat[2*k+2]); } } void add(ll k,T x){//位置kの要素に加算 k+=n-1; dat[k]+=x; while(k>0){ k=(k-1)/2; dat[k]=merge_values(dat[2*k+1],dat[2*k+2]); } } T get(ll a, ll b){ //[a,b]から(最小値とか和とかを)get return query(a, b+1, 0, 0, n); } private: T query(ll a, ll b, ll k, ll lb, ll rb){ if(rb<=a || b<=lb) return te; if(a<=lb && rb<=b) return dat[k]; ll mb = (lb+rb)>>1; T vl = query(a, b, 2*k+1, lb, mb); T vr = query(a, b, 2*k+2, mb, rb); return merge_values(vl, vr); } }; auto make_segtree = [](ll N){ //点更新と区間和 using T=ll; auto merge_values=[](T&a,T&b){return mod(a+b);}; T te=0; return Segtree (N, merge_values, te); }; struct task{ ll l,r,p; }; ll po(ll i,ll p){ if(p==0)return 1; else{ i=mod(i); if(p==1)return i; if(p%2==0)return po(mod(i*i),p/2); return mod(i*po(i,p-1)); } } ll bunbo(ll n){ return po(n,i_5); } void henkan(vector&v){ sort(all(v),[](task x,task y){ if(x.l==y.l){ return x.r>y.r; } return x.lb; rep(i,0,vs-1){ if(i==vs-1)b.pb(v[i]); else{ if(v[i].r>n>>m; vectorva,vb; rep(zz,1,m){ task t;cin>>t.l>>t.r>>t.p; if(t.p==0)va.pb(t); else vb.pb(t); } ll im[n+5];memset(im,0,sizeof(im)); for(auto t:vb){ im[t.l]++; im[t.r+1]--; } rep(i,1,n+4)im[i]+=im[i-1]; ll ans1,ans2=0; { ll cnt=0; rep(i,1,n)if(im[i]>0)cnt++; ans1=po(2,cnt-vb.size()); } { vectorcomp;comp.pb(0); rep(i,1,n)if(im[i]==0)comp.pb(i); SORT(comp);ERASE(comp); for(auto &x:va){ x.l=POSL(comp,x.l); x.r=POSL(comp,x.r+1)-1; if(x.l>x.r){ cout<<0< init(cs); ep.build(init); ep.update(0,1); rep(i,1,cs-1){ ep.update(i,ep.get(bnd[i-1],i-1)*bunbo(2)); } rep(i,0,cs-1){ ll ad=mod(ep.get(i,i)*po(2,cs-1)); // cout<