/* #region header */ #pragma GCC optimize("Ofast") #include using namespace std; #ifdef LOCAL #include "/Users/takakurashokichi/Desktop/atcoder/cxx-prettyprint-master/prettyprint.hpp" void debug() { cout << endl; } template void debug(Head H, Tail... T) { cout << " " << H; debug(T...); } #else #define debug(...) 42 #endif // types using ll = long long; using ull = unsigned long long; using ld = long double; typedef pair Pl; typedef pair Pi; typedef vector vl; typedef vector vi; typedef vector vc; template using mat = vector>; typedef vector> vvi; typedef vector> vvl; typedef vector> vvc; template struct modint { int x; modint() : x(0) {} modint(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} modint &operator+=(const modint &p) { if ((x += p.x) >= mod) x -= mod; return *this; } modint &operator-=(const modint &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } modint &operator*=(const modint &p) { x = (int)(1LL * x * p.x % mod); return *this; } modint &operator/=(const modint &p) { *this *= p.inverse(); return *this; } modint operator-() const { return modint(-x); } modint operator+(const modint &p) const { return modint(*this) += p; } modint operator-(const modint &p) const { return modint(*this) -= p; } modint operator*(const modint &p) const { return modint(*this) *= p; } modint operator/(const modint &p) const { return modint(*this) /= p; } bool operator==(const modint &p) const { return x == p.x; } bool operator!=(const modint &p) const { return x != p.x; } modint inverse() const { int a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return modint(u); } modint pow(int64_t n) const { modint ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const modint &p) { return os << p.x; } friend istream &operator>>(istream &is, modint &a) { int64_t t; is >> t; a = modint(t); return (is); } static int get_mod() { return mod; } }; // abreviations #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define rep_(i, a_, b_, a, b, ...) for (ll i = (a), max_i = (b); i < max_i; i++) #define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define rrep_(i, a_, b_, a, b, ...) \ for (ll i = (b - 1), min_i = (a); i >= min_i; i--) #define rrep(i, ...) rrep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define SZ(x) ((ll)(x).size()) #define pb(x) push_back(x) #define eb(x) emplace_back(x) #define mp make_pair #define print(x) cout << x << endl #define vprint(x) \ rep(i, x.size()) cout << x[i] << ' '; \ cout << endl #define vsum(x) accumulate(all(x), 0LL) #define vmax(a) *max_element(all(a)) #define vmin(a) *min_element(all(a)) #define lb(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define ub(c, x) distance((c).begin(), upper_bound(all(c), (x))) // functions // gcd(0, x) fails. ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } template T mypow(T x, ll n) { T ret = 1; while (n > 0) { if (n & 1) (ret *= x); (x *= x); n >>= 1; } return ret; } ll modpow(ll x, ll n, const ll mod) { ll ret = 1; while (n > 0) { if (n & 1) (ret *= x); (x *= x); n >>= 1; x %= mod; ret %= mod; } return ret; } uint64_t my_rand(void) { static uint64_t x = 88172645463325252ULL; x = x ^ (x << 13); x = x ^ (x >> 7); return x = x ^ (x << 17); } ll popcnt(ull x) { return __builtin_popcountll(x); } // graph template template struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } bool operator<(const edge &r) const { return cost < r.cost; } operator int() const { return to; } }; template using Edges = vector>; template using WeightedGraph = vector>; using UnWeightedGraph = vector>; struct Timer { clock_t start_time; void start() { start_time = clock(); } int lap() { // return x ms. return (clock() - start_time) * 1000 / CLOCKS_PER_SEC; } }; /* #endregion*/ // constant #define inf 1000000005 #define INF 4000000004000000000LL #define mod 1000000007LL #define endl '\n' typedef modint mint; const long double eps = 0.000001; const long double PI = 3.141592653589793; // library template struct LazySegmentTree { using F = function; using G = function; using H = function; int sz, height; vector data; vector lazy; const F f; const G g; const H h; const Monoid M1; const OperatorMonoid OM0; LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &M1, const OperatorMonoid OM0) : f(f), g(g), h(h), M1(M1), OM0(OM0) { sz = 1; height = 0; while (sz < n) sz <<= 1, height++; data.assign(2 * sz, M1); lazy.assign(2 * sz, OM0); } void set(int k, const Monoid &x) { data[k + sz] = x; } void build() { for (int k = sz - 1; k > 0; k--) { data[k] = f(data[2 * k + 0], data[2 * k + 1]); } } inline void propagate(int k) { if (lazy[k] != OM0) { lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]); lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]); data[k] = reflect(k); lazy[k] = OM0; } } inline Monoid reflect(int k) { return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]); } inline void recalc(int k) { while (k >>= 1) data[k] = f(reflect(2 * k + 0), reflect(2 * k + 1)); } inline void thrust(int k) { for (int i = height; i > 0; i--) propagate(k >> i); } void update(int a, int b, const OperatorMonoid &x) { thrust(a += sz); thrust(b += sz - 1); for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) lazy[l] = h(lazy[l], x), ++l; if (r & 1) --r, lazy[r] = h(lazy[r], x); } recalc(a); recalc(b); } Monoid query(int a, int b) { thrust(a += sz); thrust(b += sz - 1); Monoid L = M1, R = M1; for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) L = f(L, reflect(l++)); if (r & 1) R = f(reflect(--r), R); } return f(L, R); } Monoid operator[](const int &k) { return query(k, k + 1); } template int find_subtree(int a, const C &check, Monoid &M, bool type) { while (a < sz) { propagate(a); Monoid nxt = type ? f(reflect(2 * a + type), M) : f(M, reflect(2 * a + type)); if (check(nxt)) a = 2 * a + type; else M = nxt, a = 2 * a + 1 - type; } return a - sz; } template int find_first(int a, const C &check) { Monoid L = M1; if (a <= 0) { if (check(f(L, reflect(1)))) return find_subtree(1, check, L, false); return -1; } thrust(a + sz); int b = sz; for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if (a & 1) { Monoid nxt = f(L, reflect(a)); if (check(nxt)) return find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } template int find_last(int b, const C &check) { Monoid R = M1; if (b >= sz) { if (check(f(reflect(1), R))) return find_subtree(1, check, R, true); return -1; } thrust(b + sz - 1); int a = sz; for (b += sz; a < b; a >>= 1, b >>= 1) { if (b & 1) { Monoid nxt = f(reflect(--b), R); if (check(nxt)) return find_subtree(b, check, R, true); R = nxt; } } return -1; } void show() { rep(i, sz) cout << query(i, i + 1) << ' '; cout << endl; } }; ////condition 左から作用するイメージ // x*em = x //(x1・x2)*m = (x1*m)・(x2*m) ・ = +の時は注意 //(x1*m1)*m2 = x*(m1×2m) ////X:monoid, M:operator using X = mint; using M = mint; ////モノイドのマージ // auto fx = [](X x1, X x2){return min(x1, x2);};//min // auto fx = [](X x1, X x2){return max(x1, x2);};//max ////モノイドと作用素のマージ // auto fa = [](X x, M m){return m;};//replace // auto fa = [](X x, M m){return m+x;};//sum ////作用素のマージ // auto fm = [](M m1, M m2){return m2;};//replace // auto fm = [](M m1, M m2){return m1+m2;};//sum ////fp = m**n // auto fp = [](M m, long long n){ return m * n; };//sum // auto fp = [](M m, long long n){ return m; };//min or max ////example // LazySegTree seg(n, fx, fa, fm, fp, ex, em); ////range sum query using P = pair; ////モノイドのマージ 範囲を持たせる auto fx = [](P a, P b) { return P(a.first + b.first, a.second + b.second); }; // sum ////モノイドと作用素のマージ 範囲を持たせる auto fa = [](P a, M b) { return P(a.first * b, a.second); }; // replace // auto fa=[](P a,M b){return P(a.first+a.second*b,a.second);};//add ////作用素のマージ(上と同じ) // auto fm = [](M m1, M m2){return m2;};//replace auto fm = [](M m1, M m2) { return m1 * m2; }; // a ////単位元 ex.second = 1 // P ex = P(0, 0);//初期値はP(0, 1)にすること // LazySegmentTree seg(n, fx, fa, fm, fp, ex, em); int main() { cin.tie(0); ios::sync_with_stdio(0); cout << setprecision(20); int n, m; cin >> n >> m; vl inv(n, -1), l(n), r(n), p(n); vl nonZero(n + 1); rep(i, n) { cin >> l[i] >> r[i] >> p[i]; l[i]--; r[i]--; if (p[i] != 0) { nonZero[l[i]]++; nonZero[r[i] + 1]--; } inv[r[i]] = i; } rep(i, n) nonZero[i + 1] += nonZero[i]; auto f = [&](mint a, mint b) { return a + b; }; LazySegmentTree seg(n + 1, fx, fa, fm, P(0, 0), 1); rep(i, n + 1) seg.set(i, P(1, 1)); seg.build(); rep(i, 1, n + 1) { if (nonZero[i - 1] > 0) { seg.update(i, i + 1, 0); if (inv[i - 1] == -1) { seg.update(0, i, 2); } else { if (p[inv[i - 1]] == 0) { seg.update(0, i, 2); seg.update(0, l[inv[i - 1]], 0); } } } else { seg.update(i, i + 1, seg.query(0, i).first); seg.update(0, i, 2); if (inv[i - 1] != -1) { if (p[inv[i - 1]] == 0) { seg.update(0, l[inv[i - 1]], 0); } } } // seg.show(); } print(seg.query(0, n + 1).first); }