#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define llint long long #define inf 1e18 #define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++) #define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define mod 1000000007 using namespace std; // range-add, range-min query struct LazySegTree{ int size; vector seg, delay; LazySegTree(){} LazySegTree(int size){ this->size = size; seg.resize(1<<(size+1)); delay.resize(1<<(size+1)); } void init() { for(int i = 0; i < (1<<(size+1)); i++){ seg[i] = 0; delay[i] = 1; } } void eval(int l, int r, int k) { if(delay[k] != 1){ seg[k] *= delay[k], seg[k] %= mod; //総和クエリのときは区間幅を乗じる必要がある if(l < r){ delay[k*2] *= delay[k], delay[k*2] %= mod; delay[k*2+1] *= delay[k], delay[k*2+1] %= mod; } delay[k] = 1; } } void update(int i, llint val) { int l = 0, r = (1<= 0; j--){ k <<= 1; if(i & (1< 1){ i /= 2; seg[i] = (seg[i*2] + seg[i*2+1]) % mod; } } void add(int a, int b, int k, int l, int r, llint val) { eval(l, r, k); if(b < l || r < a) return; if(a <= l && r <= b){ delay[k] *= val, delay[k] %= mod; eval(l, r, k); return; } add(a, b, k*2, l, (l+r)/2, val); add(a, b, k*2+1, (l+r)/2+1, r, val); seg[k] = (seg[k*2] + seg[k*2+1]) % mod; } void add(int a, int b, llint val){ if(a > b) return; add(a, b, 1, 0, (1<> n >> m; for(int i = 1; i <= m; i++){ cin >> l[i] >> r[i] >> p[i]; L[r[i]] = l[i], P[r[i]] = p[i]; } seg.init(); seg.update(0, 1); for(int i = 1; i <= n; i++){ if(L[i] == 0){ seg.update(i, seg.query(0, i-1)); seg.add(0, i-1, 2); } else{ if(P[i] == 0){ seg.update(i, seg.query(0, i-1)); seg.add(0, L[i]-1, 0); seg.add(L[i], i-1, 2); } else seg.add(L[i], i-1, 0); } //for(int i = 0; i <= n; i++) cout << seg.query(i, i) << " "; cout << endl; } llint ans = seg.query(0, n); cout << ans << endl; return 0; }