""" Rが違うのを利用する→右端で+- and 0を調整できる 多分imos法 0でない区間に突入していたら0を置かない 0の区間の帳尻合わせは? 最後に0を置いたindexで管理? dp[最後に0を置いたindex] = 満たす通り数 で管理できる? 1の区間の右端はどうせ1通りに決まる 0の区間の右端は、最後に0を置いたindexにより分岐 なんの区間にも属さない→3^?を最後に掛ければいい -1 or 1の区間(中間)→どちらか好きな方を置く(2) -1 or 1の区間(最期)→決まったほうを置く(1) 0の区間(中間) → -1,0,1好きなのを置ける 0を置いた場合、dpを更新 0の区間(最期) → 0を一度でも置いていた場合は自由、そうでない場合は0 dpを1箇所更新する & 全体に掛ける なので、dp配列に入れた時点でかけていた数字が分ればなんとかなる? 全体にかけている数字Xを用意していおいて,実際のdp配列には realdp[i] * inv(X)を入れておけばいい 取り出すときはXをかけ、戻すときはinvXを書ける →普通のセグ木で解ける """ #0-indexed , 半開区間[a,b) #calc変更で演算変更 class SegTree: def __init__(self,N,first): self.NO = 2**(N-1).bit_length() self.First = first self.data = [first] * (2*self.NO) def calc(self,l,r): return l+r def update(self,ind,x): ind += self.NO - 1 self.data[ind] = x while ind >= 0: ind = (ind - 1)//2 self.data[ind] = self.calc(self.data[2*ind+1],self.data[2*ind+2]) def query(self,l,r): L = l + self.NO R = r + self.NO s = self.First while L < R: if R & 1: R -= 1 s = self.calc(s , self.data[R-1]) if L & 1: s = self.calc(s , self.data[L-1]) L += 1 L >>= 1 R >>= 1 return s def inverse(a,mod): #aのmodを法にした逆元を返す return pow(a,mod-2,mod) from sys import stdin import sys N,M = map(int,stdin.readline().split()) T = SegTree(N+1,0) T.update(0,1) mod = 10**9+7 X = 1 R = [ (None,None) for i in range(N+1) ] OS = [0] * (N+1) #1or-1の区間開始を告げる for loop in range(M): l,r,p = map(int,stdin.readline().split()) R[r] = (l,abs(p)) if p != 0: OS[l] += 1 of = 0 LEFT = 0 half = inverse(2,mod) for i in range(1,N+1): of += OS[i] l,p = R[i] #print (i,of) if p == 1: of -= 1 continue elif of == 0: tmpsum = T.query(LEFT,i) * half T.update(i,tmpsum % mod) X *= 2 X %= mod else: X *= 2 X %= mod #切り捨てフェーズ if p == 0: LEFT = l #print (LEFT,X) print (T.query(LEFT,N+1) * X % mod)