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



Sample input:
3 1
1 3 3


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:
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))

dp=[[[0 for i in range(N+1)] 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 x==1:
                if i-1>=l>j:
                    check&=1
                elif i==l:
                    check&=7
                else:
                    check=0
            elif x==2:
                if i==l:
                    check=0
                elif i-1>=l>j:
                    check&=6
                elif j>=l>k:
                    check&=3
                else:
                    check=0
            else:
                if i==l:
                    check=0
                elif i-1>=l>j:
                    check=0
                elif j>=l>k:
                    check&=4
        dp[i][j][k]=bin(check).count("1")

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

print(dp[1][0][0])

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
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 i in range(n+1)] for j in range(n+1)] for k 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)

Submission status: Time Limit Exceeded

Solution code:
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 = [[[-1 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 1
ptr = 0
for r in range(1,n+1):
  while ptr < m and lrx[ptr][1] < r:
    ptr += 1
  for g in range(r):
    for b in range(max(1,g)):
      for x,y,z in permutations((r,g,b)):
        dp[x][y][z] = 0
  while ptr < m and lrx[ptr][1] == r:
    l,_,t = lrx[ptr]
    if t != 1:
      for g in range(l):
        for b in range(max(1,g)):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
    if t != 2:
      for g in range(l,r):
        for b in range(l):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
    if t != 3:
      for g in range(l,r):
        for b in range(l,g):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
    ptr += 1
for r in range(n):
  for g in range(n):
    for b in range(n):
      mx = max(r,g,b)
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[mx+1][g][b] >= 0:
        dp[mx+1][g][b] += v
        dp[mx+1][g][b] %= mod
      if dp[r][mx+1][b] >= 0:
        dp[r][mx+1][b] += v
        dp[r][mx+1][b] %= mod
      if dp[r][g][mx+1] >= 0:
        dp[r][g][mx+1] += v
        dp[r][g][mx+1] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    for x,y,z in permutations((n,i,j)):
      if dp[x][y][z] >= 0:
        ans += dp[x][y][z]
        ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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 = [[[-1 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 1
ptr = 0
for r in range(1,n+1):
  while lrx[ptr][1] < r:
    ptr += 1
  while lrx[ptr][1] == r:
    l,_,x = lrx[ptr]
    if x == 1:
      for g in range(l):
        for b in range(g):
          for x,y,z in permutations((r,g,b)):
            dp[r][g][b] = 0
    elif x == 2:
      for g in range(l,r):
        for b in range(l):
          for x,y,z in permutations((r,g,b)):
            dp[r][g][b] = 0
    elif x == 3:
      for g in range(l,r):
        for b in range(l,g):
          for x,y,z in permutations((r,g,b)):
            dp[r][g][b] = 0

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

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

st = [[] for _ in range(n + 1)]

for _ in range(m):
    l, r, x = map(int, input().split())
    st[r].append((l, x))

dp = [[[0 for k in range(n + 1)] for j in range(n + 1)] for i in range(n + 1)]
dp[0][0][0] = 1

for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n + 1):
            if 0 < i and (i == j or i == k):
                dp[i][j][k] = 0
            if 0 < j and (j == i or j == k):
                dp[i][j][k] = 0
            if 0 < k and (k == i or k == j):
                dp[i][j][k] = 0

            l = min(i, j, k)
            r = max(i, j, k)
            c = i + j + k - l - r

            for p in st[r]:
                if p[1] == 1:
                    if c >= p[0]:
                        dp[i][j][k] = 0
                elif p[1] == 2:
                    if c < p[0] or l >= p[0]:
                        dp[i][j][k] = 0
                elif p[1] == 3:
                    if l < p[0]:
                        dp[i][j][k] = 0
            
            if r < n:
                dp[r + 1][j][k] = (dp[r + 1][j][k] + dp[i][j][k]) % MOD
                dp[i][r + 1][k] = (dp[i][r + 1][k] + dp[i][j][k]) % MOD
                dp[i][j][r + 1] = (dp[i][j][r + 1] + dp[i][j][k]) % MOD

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue

        ans = (ans + dp[i][j][n] + dp[i][n][j] + dp[n][i][j]) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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]*(N+3) for _ in range(N+3)] for _ in range(N+3)]
dp[0][1][2] = 1

for i in range(2, N+2):
    
    r = i
    for g in range(r):
        for b in range(g):
            d = dp[r][g][b]
            dp[r+1][g][b] = (dp[r+1][g][b] + d)%MOD
            dp[r][r+1][b] = (dp[r][r+1][b] + d)%MOD
            dp[r][g][r+1] = (dp[r][g][r+1] + d)%MOD
    for b in range(r):
        for g in range(b):
            d = dp[r][g][b]
            dp[r+1][g][b] = (dp[r+1][g][b] + d)%MOD
            dp[r][r+1][b] = (dp[r][r+1][b] + d)%MOD
            dp[r][g][r+1] = (dp[r][g][r+1] + d)%MOD
    
    g = i
    for r in range(g):
        for b in range(r):
            d = dp[r][g][b]
            dp[g+1][g][b] = (dp[g+1][g][b] + d)%MOD
            dp[r][g+1][b] = (dp[r][g+1][b] + d)%MOD
            dp[r][g][g+1] = (dp[r][g][g+1] + d)%MOD
    for b in range(g):
        for r in range(b):
            d = dp[r][g][b]
            dp[g+1][g][b] = (dp[g+1][g][b] + d)%MOD
            dp[r][g+1][b] = (dp[r][g+1][b] + d)%MOD
            dp[r][g][g+1] = (dp[r][g][g+1] + d)%MOD
    
    b = i
    for r in range(b):
        for g in range(r):
            d = dp[r][g][b]
            dp[b+1][g][b] = (dp[b+1][g][b] + d)%MOD
            dp[r][b+1][b] = (dp[r][b+1][b] + d)%MOD
            dp[r][g][b+1] = (dp[r][g][b+1] + d)%MOD
    for g in range(b):
        for r in range(g):
            d = dp[r][g][b]
            dp[b+1][g][b] = (dp[b+1][g][b] + d)%MOD
            dp[r][b+1][b] = (dp[r][b+1][b] + d)%MOD
            dp[r][g][b+1] = (dp[r][g][b+1] + 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):
                    dp[r][g][b] = 0
        for b in range(r):
            for g in range(b):
                if viol(b, g, l, x):
                    dp[r][g][b] = 0
        g = i+1
        for r in range(g):
            for b in range(r):
                if viol(r, b, l, x):
                    dp[r][g][b] = 0
        for b in range(g):
            for r in range(b):
                if viol(b, r, l, x):
                    dp[r][g][b] = 0
        b = i+1
        for r in range(b):
            for g in range(r):
                if viol(r, g, l, x):
                    dp[r][g][b] = 0
        for g in range(b):
            for r in range(g):
                if viol(g, r, l, x):
                    dp[r][g][b] = 0
res = 0
for r in range(N+3):
    for g in range(N+3):
        for b in range(N+3):
            if max(r, g, b) == 2+N:
                res = (res + dp[r][g][b])%MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
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)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    ans = 0
    for r in range(n):
        for g in range(n):
            for b in range(n):
                pre = dp[r][g][b]
                if pre == 0: continue
                i = max(r, g, b) + 1
                flag=False
                for l, x in rtol[i-1]:
                    over_l = [r >= l, g >= l, b >= l]
                    if sum(over_l)!=x:
                        flag=True
                        break
                if flag:continue
                dp[i][g][b] = (pre+dp[i][g][b])%md
                dp[r][i][b] = (pre+dp[r][i][b])%md
                dp[r][g][i] = (pre+dp[r][g][i])%md
    for l, x in rtol[n]:
        for i in range(n):
            for j in range(n):
                over_l = [i >= l, j >= l]
                if sum(over_l)+1 != x:
                    dp[i][j][n]=0
                    dp[i][n][j]=0
                    dp[n][j][i]=0

    ans+=sum(dp[i][j][n] for i in range(n) for j in range(n))
    ans%=md
    ans+=sum(dp[i][n][j] for i in range(n) for j in range(n))
    ans%=md
    ans+=sum(dp[n][j][i] for i in range(n) for j in range(n))
    ans%=md
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
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)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    ans = 0
    for r in range(n):
        for g in range(n):
            for b in range(n):
                pre = dp[r][g][b]
                if pre == 0: continue
                i = max(r, g, b) + 1
                dp[i][g][b] = (pre+dp[i][g][b])%md
                dp[r][i][b] = (pre+dp[r][i][b])%md
                dp[r][g][i] = (pre+dp[r][g][i])%md
                for l, x in rtol[i]:
                    over_l = [r >= l, g >= l, b >= l]
                    if over_l[1] + over_l[2] + 1 != x:
                        dp[i][g][b] = 0
                    if over_l[0] + over_l[2] + 1 != x:
                        dp[r][i][b] = 0
                    if over_l[0] + over_l[1] + 1 != x:
                        dp[r][g][i] = 0
                #if i == n:
                #    ans += dp[i][g][b] + dp[r][i][b] + dp[r][g][i]
    ans+=sum(dp[i][j][n] for i in range(n) for j in range(n))
    ans%=md
    ans+=sum(dp[i][n][j] for i in range(n) for j in range(n))
    ans%=md
    ans+=sum(dp[n][j][i] for i in range(n) for j in range(n))
    ans%=md
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
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)] for _ in range(n + 1)]
    dp[0][0][0] = 1
    ans = 0
    for r in range(n):
        for g in range(n):
            for b in range(n):
                pre = dp[r][g][b]
                if pre == 0: continue
                i = max(r, g, b) + 1
                dp[i][g][b] += pre
                dp[r][i][b] += pre
                dp[r][g][i] += pre
                for l, x in rtol[i]:
                    over_l = [r >= l, g >= l, b >= l]
                    if over_l[1] + over_l[2] + 1 != x:
                        dp[i][g][b] = 0
                    if over_l[0] + over_l[2] + 1 != x:
                        dp[r][i][b] = 0
                    if over_l[0] + over_l[1] + 1 != x:
                        dp[r][g][i] = 0
                #if i == n:
                #    ans += dp[i][g][b] + dp[r][i][b] + dp[r][g][i]
    ans+=sum(dp[i][j][n] for i in range(n) for j in range(n))
    ans%=md
    ans+=sum(dp[i][n][j] for i in range(n) for j in range(n))
    ans%=md
    ans+=sum(dp[n][j][i] for i in range(n) for j in range(n))
    ans%=md
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import combinations
from collections import defaultdict

MOD = 1000000007  # type: int

def solve(N: int, M: int, l: "List[int]", r: "List[int]", x: "List[int]"):
    q = [(0, 0, b) for b in range(N+1)]
    q.extend([(r, g, b) for r, g, b in combinations(range(N+1), 3)])
    q.sort(key=lambda a: a[-1])

    dp = {t: 0 for t in q}
    dp[(0, 0, 0)] = 1

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

    for r, g, b in q:
        for cl, x in conditions[b]:
            if x == 1 and g < cl:
                continue
            if x == 2 and r < cl and g >= cl:
                continue
            if x == 3 and r >= cl:
                continue
            dp[(r, g, b)] = 0

        if b == N:
            continue

        dp[(g, b, b+1)] += dp[(r, g, b)]
        dp[(g, b, b+1)] %= MOD
        dp[(r, b, b+1)] += dp[(r, g, b)]
        dp[(r, b, b+1)] %= MOD
        dp[(r, g, b+1)] += dp[(r, g, b)]
        dp[(r, g, b+1)] %= MOD

    res = 0
    for g in range(N):
        for r in range(g):
            res = (res + dp[(r, g, N)]) % MOD
    res += dp[(0, 0, N)]
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    l = [int()] * (M)  # type: "List[int]" 
    r = [int()] * (M)  # type: "List[int]" 
    x = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, M, l, r, x)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product
from collections import defaultdict

MOD = 1000000007  # type: int

def solve(N: int, M: int, l: "List[int]", r: "List[int]", x: "List[int]"):
    dp = {(r, g, b): 0 for r, g, b in product(range(N+1), repeat=3)}
    dp[(0, 0, 0)] = 1

    q = [(r, g, b, max(r, g, b)) for r, g, b in product(range(N+1), repeat=3)]
    q.sort(key=lambda x: x[-1])

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

    for r, g, b, k in q:
        for cl, x in conditions[k]:
            temp = sorted((r, g, b))
            if x == 1 and temp[1] < cl:
                continue
            if x == 2 and temp[0] < cl and temp[1] >= cl:
                continue
            if x == 3 and temp[0] >= cl:
                continue
            dp[(r, g, b)] = 0

        if k == N:
            continue

        dp[(k+1, g, b)] += dp[(r, g, b)]
        dp[(k+1, g, b)] %= MOD
        dp[(r, k+1, b)] += dp[(r, g, b)]
        dp[(r, k+1, b)] %= MOD
        dp[(r, g, k+1)] += dp[(r, g, b)]
        dp[(r, g, k+1)] %= MOD

    res = 0
    for i in range(N):
        for j in range(N):
            res = (res + dp[(N,i,j)]) % MOD
            res = (res + dp[(j,N,i)]) % MOD
            res = (res + dp[(i,j,N)]) % MOD
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    l = [int()] * (M)  # type: "List[int]" 
    r = [int()] * (M)  # type: "List[int]" 
    x = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, M, l, r, x)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product
from collections import defaultdict

MOD = 1000000007  # type: int

def add(*L):
    return sum(L) % MOD

def solve(N: int, M: int, l: "List[int]", r: "List[int]", x: "List[int]"):
    dp = {(r, g, b): 0 for r, g, b in product(range(N+1), repeat=3)}
    dp[(0, 0, 0)] = 1

    q = [(r, g, b, max(r, g, b)) for r, g, b in product(range(N+1), repeat=3)]
    q.sort(key=lambda x: x[-1])

    conditions = defaultdict(list)
    for l, r, x in zip(l, r, x):
        conditions[r].append((l, x))
    
    for r, g, b, k in q:
        for cl, x in conditions[k]:
            temp = sorted((r, g, b))
            if x == 1 and temp[1] < cl:
                continue
            if x == 2 and temp[0] < cl and temp[1] >= cl:
                continue
            if x == 3 and temp[0] >= cl:
                continue
            dp[(r, g, b)] = 0

        if k == N:
            continue

        dp[(k+1, g, b)] += dp[(r, g, b)]
        dp[(k+1, g, b)] %= MOD
        dp[(r, k+1, b)] += dp[(r, g, b)]
        dp[(r, k+1, b)] %= MOD
        dp[(r, g, k+1)] += dp[(r, g, b)]
        dp[(r, g, k+1)] %= MOD           
    
    res = 0
    for i in range(N):
        for j in range(N):
            res = (res + dp[(N,i,j)]) % MOD
            res = (res + dp[(j,N,i)]) % MOD
            res = (res + dp[(i,j,N)]) % MOD
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    l = [int()] * (M)  # type: "List[int]" 
    r = [int()] * (M)  # type: "List[int]" 
    x = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
        x[i] = int(next(tokens))
    solve(N, M, l, r, x)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)]
                           
for a in range(N+1):
  for b in range(max(1,a)):
    for c in range(max(1,b)):
      dp[a].append([[0]*(c+1) for i in range(b+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(b):
    ans+=dp[N][b][c]
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
rec = defaultdict(list)
mod = 10 ** 9 + 7
for i in range(m):
    l, r, x = map(int, input().split())
    rec[r].append((l, x))

dp = [[[0] * (n + 1) for j in range(n + 1)] * n for i in range(n + 1)]
dp[0][0][0] = 1
for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n + 1):
            flag = True
            if (i != 0 and i == j) or (j != 0 and j == k) or (k != 0 and k == i):
                continue
            q = max(max(i, j), k)
            for a, b in rec[q]:
                tmp = 0
                if a <= i:
                    tmp += 1
                if a <= j:
                    tmp += 1
                if a <= k:
                    tmp += 1
                if tmp != b:
                    dp[i][j][k] = 0
                    flag = False
                    break
            if flag and q + 1 <= n:
                dp[q + 1][j][k] += dp[i][j][k]
                dp[i][q + 1][k] += dp[i][j][k]
                dp[i][j][q + 1] += dp[i][j][k]
                if dp[q + 1][j][k] >= mod:
                    dp[q + 1][j][k] -= mod
                if dp[i][q + 1][k] >= mod:
                    dp[i][q + 1][k] -= mod
                if dp[i][j][q + 1] >= mod:
                    dp[i][j][q + 1] -= mod

num = 0
for i in range(n):
    for j in range(n):
        num += dp[n][i][j]
        num += dp[i][n][j]
        num += dp[i][j][n]
        num %= mod

print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
rec = defaultdict(list)
mod = 10 ** 9 + 7
for i in range(m):
    l, r, x = map(int, input().split())
    rec[r].append((l, x))

dp = [[[0] * (n + 1) for j in range(n + 1)] * n for i in range(n + 1)]
dp[0][0][0] = 1
for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n + 1):
            flag = True
            if (i != 0 and i == j) or (j != 0 and j == k) or (k != 0 and k == i):
                continue
            q = max(max(i, j), k)
            for a, b in rec[q]:
                tmp = 0
                if a <= i:
                    tmp += 1
                if a <= j:
                    tmp += 1
                if a <= k:
                    tmp += 1
                if tmp != b:
                    dp[i][j][k] = 0
                    flag = False
                    break
            if flag and q + 1 <= n:
                dp[q + 1][j][k] += dp[i][j][k]
                dp[i][q + 1][k] += dp[i][j][k]
                dp[i][j][q + 1] += dp[i][j][k]

num = 0
for i in range(n):
    for j in range(n):
        num += dp[n][i][j]
        num += dp[i][n][j]
        num += dp[i][j][n]
        num %= mod

print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
rec = defaultdict(list)
mod = 10 ** 9 + 7
for i in range(m):
    l, r, x = map(int, input().split())
    rec[r].append((l, x))

dp = [[[0] * (n + 1) for j in range(n + 1)] * n for i in range(n + 1)]
dp[0][0][0] = 1
for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n + 1):
            flag = True
            if (i != 0 and i == j) or (j != 0 and j == k) or (k != 0 and k == i):
                continue
            q = max(max(i, j), k)
            for a, b in rec[q]:
                tmp = 0
                if a <= i:
                    tmp += 1
                if a <= j:
                    tmp += 1
                if a <= k:
                    tmp += 1
                if tmp != b:
                    dp[i][j][k] = 0
                    flag = False
                    break
            if flag and q + 1 <= n:
                dp[q + 1][j][k] += dp[i][j][k]
                dp[i][q + 1][k] += dp[i][j][k]
                dp[i][j][q + 1] += dp[i][j][k]
                dp[q + 1][j][k] %= mod
                dp[i][q + 1][k] %= mod
                dp[i][j][q + 1] %= mod


num = 0
for i in range(n):
    for j in range(n):
        num += dp[n][i][j]
        num += dp[i][n][j]
        num += dp[i][j][n]
        num %= mod

print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
rec = defaultdict(list)
mod = 10 ** 9 + 7
for i in range(m):
    l, r, x = map(int, input().split())
    rec[r].append((l, x))

dp = [[[0] * (n + 1) for j in range(n + 1)] * n for i in range(n + 1)]
dp[0][0][0] = 1
for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n + 1):
            if (i != 0 and i == j) or (j != 0 and j == k) or (k != 0 and k == i):
                continue
            q = max(max(i, j), k)
            for a, b in rec[q]:
                tmp = 0
                if a <= i:
                    tmp += 1
                if a <= j:
                    tmp += 1
                if a <= k:
                    tmp += 1
                if tmp != b:
                    dp[i][j][k] = 0
            if q + 1 <= n:
                dp[q + 1][j][k] += dp[i][j][k]
                dp[i][q + 1][k] += dp[i][j][k]
                dp[i][j][q + 1] += dp[i][j][k]
                dp[q + 1][j][k] %= mod
                dp[i][q + 1][k] %= mod
                dp[i][j][q + 1] %= mod


num = 0
for i in range(n):
    for j in range(n):
        num += dp[n][i][j]
        num += dp[i][n][j]
        num += dp[i][j][n]
        num %= mod

print(num)