Problem:
 Score : 800 points    Problem Statement 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 1 3 1
1 3 3      Sample Output 1 6  The six ways are:   RGB  RBG  GRB  GBR  BRG  BGR   where R, G and B correspond to red, green and blue squares, respectively.       Sample Input 2 4 2
1 3 1
2 4 2      Sample Output 2 6  The six ways are:   RRRG  RRRB  GGGR  GGGB  BBBR  BBBG        Sample Input 3 1 3
1 1 1
1 1 2
1 1 3      Sample Output 3 0  There are zero ways.       Sample Input 4 8 10
2 6 2
5 5 1
3 5 2
4 7 3
4 4 1
2 3 1
7 7 1
1 5 2
1 7 3
3 4 2      Sample Output 4 108

Solution (Python):
import sys
input = sys.stdin.readline

mod = 10**9+7




def check(i, j, l, x):
    return (x == 3 and l <= i) or (x == 2 and i < l <= j) or (x == 1 and j < l)


N, M = map(int, input().split())
LRX = [list(map(int, input().split())) for _ in range(M)]

LX = [[] for _ in range(N+2)]
for l, r, x in LRX:
    LX[r].append((l, x))

dp = [[[0]*(j+1) for j in range(i+1)] for i in range(N+2)]



dp[0][0][0] = 1

for i in range(N+1):
    for j in range(i, N+1):
        for k in range(j, N+1):
            
            
            ok = True
            for l, x in LX[k+1]:
                if not check(j, k, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][k][j] = (dp[k+1][k][j] + dp[k][j][i]) % mod
            
            
            ok = True
            for l, x in LX[k+1]:
                if not check(i, j, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][j][i] = (dp[k+1][j][i] + dp[k][j][i]) % mod
            
            
            ok = True
            for l, x in LX[k+1]:
                if not check(i, k, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][k][i] = (dp[k+1][k][i] + dp[k][j][i]) % mod
        

ans = 0
for a in range(N+1):
    for b in range(a,N+1):
        ans = (ans + dp[N][b][a]) % mod

print(ans)

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m = map(int,readline().split())


cond = [[] for _ in range(n+1)]
for _ in range(m):
    l,r,x = map(int,readline().split())
    cond[r].append((l,x))

"""
dp[i][j][k] = iまで見て 2 色目は j個前に、3 色目は k個前 に登場
1 <= j < k
"""
N = n+3
dp = [[0]*(N) for _ in range(N)]
dp[1][2] = 1

MOD = 10**9+7

def f(r,j,k,v,ndp):
    if j >= N or k >= N: return
    for l,x in cond[r]:
        if x==1 and l <= r-j: return
        if x==2 and (r-j < l or l <= r-k): return
        if x==3 and r-k < l: return
    ndp[j][k] += v
    ndp[j][k] %= MOD
    return

for i in range(1,n+1):
    ndp = [[0]*(N) for _ in range(N)]
    for q in range(1,N):
        for r in range(q+1,N):
            v = dp[q][r]
            if v:
                f(i,q+1,r+1,v,ndp)
                f(i,1,r+1,v,ndp)
                f(i,1,q+1,v,ndp)
    dp = ndp
    



ans = sum(sum(i) for i in dp)
print(ans%MOD)

Solution (Python):
N,M=map(int,input().split())
q=[[] for i in range(N+1)]
for i in range(M):
    l,r,x=map(int,input().split())
    q[r].append((l,x))
mod=10**9+7

dp=[[0 for i in range(N+1)] for i in range(N+1)]

i=N
for j in range(N+1):
    for k in range(N+1):
        check=7
        for l,x in q[i]:
            if i==l:
                check=(x==1)*check
            elif i-1>=l>j:
                check=(x==1)*(check%2)+(x==2)*(check&6)
            elif j>=l>k:
                check=(x==2)*(check&3)+(x==3)*(check&4)
            else:
                check*=(x==3)
        dp[j][k]=bin(check).count("1")

ndp=[[0 for j in range(N+1)] for k in range(N+1)]
for i in range(N-1,0,-1):
    for j in range(i):
        for k in range(j+1):
            check=7
            for l,x in q[i]:
                if i==l:
                    check=(x==1)*check
                elif i-1>=l>j:
                    check=(x==1)*(check%2)+(x==2)*(check&6)
                elif j>=l>k:
                    check=(x==2)*(check&3)+(x==3)*(check&4)
                else:
                    check*=(x==3)
            ndp[j][k]=(dp[j][k]*((check//1)%2)+dp[i-1][k]*((check//2)%2)+dp[i-1][j]*((check//4)%2))%mod

    dp=ndp

print(dp[0][0])

Solution (Python):
from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for b in range(max(1,g))] for g in range(max(1,r))] for r in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        dp[r][g][b] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        dp[r][g][b] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        dp[r][g][b] = -1

for r in range(n):
  for g in range(max(1,r)):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
      if dp[r+1][r][b] >= 0:
        dp[r+1][r][b] += v
        dp[r+1][r][b] %= mod
      if dp[r+1][r][g] >= 0:
        dp[r+1][r][g] += v
        dp[r+1][r][g] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    if dp[n][i][j] >= 0:
      ans += dp[n][i][j]
      ans %= mod
print(ans%mod)

Solution (Python):
import sys
readline = sys.stdin.readline

def viol(c2, c3, l, x):
    res = False
    if x == 1:
        if not c2 < l:
            res = True
    elif x == 2:
        if not c3 < l <= c2:
            res = True
    else:
        if not l <= c3:
            res = True
    return res
MOD = 10**9+7
N, M = map(int, readline().split())
limit = [[] for _ in range(N+3)]

for _ in range(M):
    l, r, x = map(int, readline().split())
    limit[r+2].append((l+2, x))

dp = [[0, 0], [1, 0]]

for i in range(2, N+2):    
    dp2 = [[0]*(i+1) for _ in range(i+1)]
    r = i
    for g in range(r):
        for b in range(g):
            d = dp[g][b]
            dp2[g][b] = (dp2[g][b] + d)%MOD
            dp2[r][b] = (dp2[r][b] + d)%MOD
            dp2[r][g] = (dp2[r][g] + d)%MOD
    for l, x in limit[i+1]:
        r = i+1
        for g in range(r):
            for b in range(g):
                if viol(g, b, l, x):
                    dp2[g][b] = 0
    dp = [d[:] for d in dp2]
    
res = 0
for g in range(N+2):
    for b in range(g):
        res = (res + dp[g][b]) % MOD
print(res)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np





MOD = 10 ** 9 + 7

N,M = map(int,readline().split())
m = map(int,read().split())
LRX = zip(m,m,m)

R_to_LX = [[] for _ in range(N+3)]
for l,r,x in LRX:
    R_to_LX[r+2].append((l+2,x))

dp = np.zeros((N+3,N+3),np.int64)
dp[1,0] = 1
for r in range(3,N+3):
    
    prev = dp
    dp = np.zeros((N+3,N+3),np.int64)
    
    dp += prev
    
    dp[r-1,:] += prev.sum(axis=0)
    
    dp[r-1,:] += prev.sum(axis=1)
    
    for l,x in R_to_LX[r]:
        if x == 1:
            dp[l:] = 0
        elif x == 2:
            
            dp[:l] = 0
            
            dp[:,l:] = 0
        else:
            
            dp[:,:l] = 0
    dp %= MOD

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

Solution (Python):
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)]


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

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

main()

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict




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))


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)

Solution (Python):
N,M=map(int,input().split())
Q=[[int(i) for i in input().split()] for i in range(M)]
Q.sort(key=lambda x:x[1])
mod=10**9+7
dp=[[[0]*max(1,c) for c in range(max(1,b+1))] for b in range(N+1)]
dp[0][0][0]=1
k=0
for a in range(N+1):
  check=[]
  if k<=M-1:
    while a==Q[k][1]:
      l,r,x=Q[k]
      check.append((l,r,x))
      k+=1
      if k==M:
        break
  for b in range(max(1,a)):
    for c in range(max(1,b)):
      for l,r,x in check:
        if x==1:
          if not b<l:
            dp[a][b][c]=0
            continue
        elif x==2:
          if not (b>=l and c<l):
            dp[a][b][c]=0
            continue
        elif x==3:
          if not c>=l:
            dp[a][b][c]=0
            continue
      dp[a][b][c]%=mod
      if a<=N-1:
        dp[a+1][b][c]+=dp[a][b][c]
        dp[a+1][a][c]+=dp[a][b][c]
        dp[a+1][a][b]+=dp[a][b][c]
ans=0
for b in range(N):
  for c in range(max(1,b)):
    ans+=dp[N][b][c]
    ans%=mod
print(ans)

Solution (Python):
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)
        exit(0)
    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)
    exit(0)

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)

Solution (Python):
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)
    exit(0)


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:
                    
                    Z[g] += v
                if t2 <= r < s1:
                    
                    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():
            
            Z[g] += v
            
            Z[r] += v;
    for z, v in enumerate(Z):
        if v:
            X[z, b] = v % MOD
print(sum(X.values()) % MOD)

Solution (Python):
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)
  exit(0)

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)

Solution (Python):
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)
  exit(0)

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)