There are N squares arranged in a row.
The squares are numbered 1, 2, ..., N, from left to right.
Snuke is painting each square in red, green or blue.
According to his aesthetic sense, the following M conditions must all be satisfied.
The i-th condition is:
 - There are exactly x_i different colors among squares l_i, l_i + 1, ..., r_i.
In how many ways can the squares be painted to satisfy all the conditions?
Find the count modulo 10^9+7.

-----Constraints-----
 - 1 ≤ N ≤ 300
 - 1 ≤ M ≤ 300
 - 1 ≤ l_i ≤ r_i ≤ N
 - 1 ≤ x_i ≤ 3

-----Input-----
Input is given from Standard Input in the following format:
N M
l_1 r_1 x_1
l_2 r_2 x_2
:
l_M r_M x_M

-----Output-----
Print the number of ways to paint the squares to satisfy all the conditions, modulo 10^9+7.

-----Sample Input-----
3 1
1 3 3

-----Sample Output-----
6

The six ways are:
 - RGB
 - RBG
 - GRB
 - GBR
 - BRG
 - BGR
where R, G and B correspond to red, green and blue squares, respectively.

Difficulty: competition

Starter code:

Solutions:
from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x))

if any(x != 1 for l,x in Q[1]):
  print(0)
  return

dp = defaultdict(int)
dp[0,0] = 3

x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  for i,(a,b) in enumerate(zip(x_sum,y_sum)):
    c = (a+b)%MOD
    dp[i,pk] = c
    x_sum[i] += c

  x_sum.append(0)
  y_sum.append((2*s)%MOD)
  s *= 3
  subQ = Q[k]

  for i,j in list(dp.keys()):
    for l,x in subQ:
      if x != (l<=i)+(l<=j)+1:
        c = dp[i,j]
        x_sum[i] -= c
        y_sum[j] -= c
        s -= c
        del dp[i,j]
        break

  for i in range(pk):
    x_sum[i] %= MOD
    y_sum[i] %= MOD
  s %= MOD

print(s)

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    return


X = {(0, 0): 3}
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]
    check = lambda r, g: t2 <= r < s1 and t1 <= g < s0

    Z = [0]*(N+1)
    if C[b+1]:
        if t1 <= b < s0:
            for (r, g), v in X.items():
                if t2 <= g < s1:
                    # r <- b+1
                    Z[g] += v
                if t2 <= r < s1:
                    # g <- b+1
                    Z[r] += v
        X = {(r, g): v for (r, g), v in X.items() if t2 <= r < s1 and t1 <= g < s0}
    else:
        Z = [0]*(N+1)
        for (r, g), v in X.items():
            # r <- b+1
            Z[g] += v
            # g <- b+1
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)

import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

# 最後に置いたものは赤とする（3倍）
# 青、緑を最後にいつ置いたのかを持ってdp

MOD = 10 ** 9 + 7
N,M = map(int,input().split())
LRX = [[int(x) for x in input().split()] for _ in range(M)]

R_to_LX = defaultdict(list)
for l,r,x in LRX:
    R_to_LX[r].append((l,x))

# 1個目を置いた時点
for n in range(1,N+1):
    if n == 1:
        dp = np.zeros((n,n), dtype = np.int64)
        dp[0,0] = 1
    else:
        prev = dp
        dp = np.zeros((n,n), dtype = np.int64)
        # 同色
        dp[:-1,:-1] = prev
        # 青から赤に
        dp[n-1,:-1] = prev.sum(axis = 0)
        # 緑から赤に
        dp[:-1,n-1] = prev.sum(axis = 1)
    # ルール違反を除外する
    for l,x in R_to_LX[n]:
        if x == 1:
            dp[l:,:] = 0
            dp[:,l:] = 0
        elif x == 2:
            dp[l:,l:] = 0
            dp[:l,:l] = 0
        elif x == 3:
            dp[:l,:] = 0
            dp[:,:l] = 0
    dp %= MOD

answer = dp.sum() * 3 % MOD
print(answer)

MOD = 10**9 + 7
N, M = map(int, input().split())
S = [[N+1]*(N+1) for i in [0,1,2]]
T = [[0]*(N+1) for i in [0,1,2]]

C = [0]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())
    if r-l < x-1:
        print(0)
        return
    S[x-1][r] = min(S[x-1][r], l)
    T[x-1][r] = max(T[x-1][r], l)
    C[r] = 1

S0, S1, S2 = S
T0, T1, T2 = T

ok = 1
for i in range(N+1):
    if not T2[i] < S1[i] or not T1[i] < S0[i]:
        ok = 0
        break

if not ok:
    print(0)
    return

RM = [N+1]*(N+1); GM = [N+1]*(N+1)
for i in range(N-1, -1, -1):
    RM[i] = min(RM[i+1], S1[i+1])
    GM[i] = min(GM[i+1], S0[i+1])


X = {(0, 0): 3}
D = [0]*(N+1); D[0] = 6
B = [{} for i in range(N+1)]
B[0][0] = 3
bb = 0
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]

    rm = RM[b]
    gm = GM[b]
    if t1 <= b < gm:
        F = B[b]
        for z in range(t2, min(rm, b)):
            v = D[z] % MOD
            if v:
                F[z] = v; D[z] += v; D[b] += v
    if C[b+1]:
        for g in range(bb, min(t1, b)):
            for r, v in B[g].items():
                D[r] -= v; D[g] -= v
            B[g] = None
        bb = max(t1, bb)
        for g in range(bb, b):
            for r, v in B[g].items():
                if not t2 <= r < s1:
                    D[r] -= v; D[g] -= v
            B[g] = {r: v for r, v in B[g].items() if t2 <= r < s1}
ans = 0
for b in range(bb, N+1):
    if B[b]:
        ans += sum(B[b].values())
print(ans % MOD)

from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x-1))

if any(x != 0 for l,x in Q[1]):
  print(0)
  return

dp = {(0,0):3}
memo = [6]
s = 3

for pk in range(1,N):
  k = pk+1

  for i,c in enumerate(memo):
    c %= MOD
    dp[i,pk] = c
    memo[i] *= 2
    memo[i] %= MOD

  memo.append(2*s%MOD)
  s = 3*s%MOD
  subQ = Q[k]

  for i,j in list(dp.keys()):
    for l,x in subQ:
      if x != (l<=i)+(l<=j):
        c = dp[i,j]
        memo[i] -= c
        memo[j] -= c
        s -= c
        del dp[i,j]
        break

  s %= MOD

print(s)

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

# 一番後ろの色を(赤に)固定した上で、もらうDPに書き換え
def main():
    md = 10 ** 9 + 7
    n, m = MI()
    rtol = defaultdict(list)
    for _ in range(m):
        l, r, x = MI()
        rtol[r].append([l, x])
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for k in range(1, n + 1):
        for i in range(k - 1):
            dp[i][k - 1] = dp[k - 1][i] = sum(dp[i][:k - 1]) % md
        for l, x in rtol[k]:
            if x == 1:
                for i in range(l, k):
                    for j in range(k):
                        dp[i][j] = dp[j][i] = 0
            if x == 2:
                for i in range(l, k):
                    for j in range(i + 1, k):
                        dp[i][j] = dp[j][i] = 0
                for i in range(l):
                    for j in range(i + 1):
                        dp[i][j] = dp[j][i] = 0
            if x == 3:
                for i in range(l):
                    for j in range(k):
                        dp[i][j] = dp[j][i] = 0

    # p2D(dp)
    print(sum(sum(dr) for dr in dp) * 3 % md)

main()