Buggy python submission (verdict: Time Limit Exceeded):
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())
    l, r = N-r+1, N-l+1
    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}
R = [0]*(N+1); R[0] = 3
G = [0]*(N+1); G[0] = 3
for b in range(1, N):
    t2 = T2[b+1]; s1 = S1[b+1]; t1 = T1[b+1]; s0 = S0[b+1]

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

Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
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())
    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}
R = [0]*(N+1); R[0] = 3
G = [0]*(N+1); G[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

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


Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
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())
    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}
R = [0]*(N+1); R[0] = 3
G = [0]*(N+1); G[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

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

Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
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:
                    # 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)

Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
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]]
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)

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): 1}
for b in range(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

    Y = {}
    for (r, g), v in X.items():
        v %= MOD
        if check(g, b):
            # r <- b+1
            Y[g, b] = Y.get((g, b), 0) + v
        if check(r, b):
            # g <- b+1
            Y[r, b] = Y.get((r, b), 0) + v
        if check(r, g):
            # b <- b+1
            Y[r, g] = Y.get((r, g), 0) + v
    X = Y
print(sum(X.values()) % MOD)

Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
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]]
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)

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): 1}
for b in range(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

    Y = {}
    for (r, g), v in X.items():
        v %= MOD
        if check(g, b):
            # r <- b+1
            Y[g, b] = Y.get((g, b), 0) + v
        if check(r, b):
            # g <- b+1
            Y[r, b] = Y.get((r, b), 0) + v
        if check(r, g):
            # b <- b+1
            Y[r, g] = Y.get((r, g), 0) + v
    X = Y
print(sum(X.values()) % MOD)

Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
free = [1]*(N+1)
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

        # r-1の時に満たすべき条件
        g_min[r-1] = max(g_min[r-1], l)

    for j in range(l, r+1):
        free[j] = 0
# rより小さいインデックスで制約が満たすべき条件を伝播して高速化
for r in range(N-1, -1, -1):
    r_max[r] = min(r_max[r], r_max[r+1])
    g_max[r] = min(g_max[r], g_max[r+1])

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    if free[k]:
        # N = 300, M = 0の場合等だと制約が少なすぎて定数が落ちない
        # => 制約が疎である場合は、制約がかかってない部分で切って高速化
        res = memo[key] = (3 * dfs(k+1, k, k, k+1)) % MOD
    else:
        # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
        res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))


Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
free = [1]*(N+1)
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)
    for j in range(l, r+1):
        free[j] = 0
# rより小さいインデックスで制約が満たすべき条件を伝播して高速化
for r in range(N-1, -1, -1):
    r_max[r] = min(r_max[r], r_max[r+1])
    g_max[r] = min(g_max[r], g_max[r+1])

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    if free[k]:
        # N = 300, M = 0の場合等だと制約が少なすぎて定数が落ちない
        # => 制約が疎である場合は、制約がかかってない部分で切って高速化
        res = memo[key] = (3 * dfs(k+1, k, k, k+1)) % MOD
    else:
        # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
        res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
free = [1]*(N+1)
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)
    for j in range(l, r+1):
        free[j] = 0

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    if free[k]:
        # N = 300, M = 0の場合等だと制約が少なすぎて定数が落ちない
        # => 制約が疎である場合は、制約がかかってない部分で切って高速化
        res = memo[key] = (3 * dfs(k+1, k, k, b+1)) % MOD
    else:
        # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
        res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))


Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

#def check(r, g, k):
#    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

# 左からk個置いた時、各色の最右の位置を持ってbfs
# r < g < b(= k) を維持して計算していく
que = [{} for i in range(N+1)]
que[0][0, 0] = 1
for k in range(N-1):
    cur = que[k]
    nxt = que[k+1]
    get = nxt.get
    rm = r_min[k+1]; rM = r_max[k+1]
    gm = g_min[k+1]; gM = g_max[k+1]
    for key, val in cur.items():
        # r < g < b < k+1 の関係を元に次の状態に伝播
        r, g = key
        val %= MOD

        # 制約を満たす場合のみに伝播
        if gm <= k <= gM:
            if rm <= g <= rM:
                nxt[g, k] = get((g, k), 0) + val
            if rm <= r <= rM:
                nxt[r, k] = get((r, k), 0) + val
        if rm <= r <= rM and gm <= g <= gM:
            nxt[key] = get(key, 0) + val

rm = r_min[N]; rM = r_max[N]
gm = g_min[N]; gM = g_max[N]
ans = 0
for key, val in que[N-1].items():
    r, g = key
    if gm <= N-1 <= gM:
        ans += val*( (rm <= r <= rM) + (rm <= g <= rM) )
    if rm <= r <= rM and gm <= g <= gM:
        ans += val
    ans %= MOD

print(ans)

Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

def check(r, g, k):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

# 左からk個置いた時、各色の最右の位置を持ってbfs
# r < g < b(= k) を維持して計算していく
que = [{} for i in range(N+1)]
que[0][0, 0] = 1
for k in range(N-1):
    cur = que[k]
    nxt = que[k+1]
    for key, val in cur.items():
        # r < g < b < k+1 の関係を元に次の状態に伝播
        r, g = key

        # 制約を満たす場合のみに伝播
        if check(g, k, k+1):
            nxt[g, k] = (nxt.get((g, k), 0) + val) % MOD
        if check(r, k, k+1):
            nxt[r, k] = (nxt.get((r, k), 0) + val) % MOD
        if check(r, g, k+1):
            nxt[r, g] = (nxt.get((r, g), 0) + val) % MOD
ans = 0
for key, val in que[N-1].items():
    r, g = key
    if check(g, N-1, N):
        ans += val
    if check(r, N-1, N):
        ans += val
    if check(r, g, N):
        ans += val
    ans %= MOD

print(ans)

Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Runtime Error):
# seishin.py
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

def check(r, g, k):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

# 左からk個置いた時、各色の最右の位置を持ってbfs
# r < g < b(= k) を維持して計算していく
que = [{} for i in range(N+1)]
que[0][0, 0] = 1
for k in range(N-1):
    cur = que[k]
    nxt = que[k+1]
    for key, val in cur.items():
        # r < g < b < k+1 の関係を元に次の状態に伝播
        r, g = key

        # 制約を満たす場合のみに伝播
        if check(g, k, k+1):
            nxt[g, k] = (nxt.get((g, k), 0) + val) % MOD
        if check(r, k, k+1):
            nxt[r, k] = (nxt.get((r, k), 0) + val) % MOD
        if check(r, g, k+1):
            nxt[r, g] = (nxt.get((r, g), 0) + val) % MOD
ans = 0
for key, val in que[N-1].items():
    r, g = key
    if check(g, k, k+1):
        ans += val
    if check(r, k, k+1):
        ans += val
    if check(r, g, k+1):
        ans += val
    ans %= MOD

print(ans)

Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

def check(r, g, k):
    return +(r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

# 左からk個置いた時、各色の最右の位置を持ってbfs
# r < g < b(= k) を維持して計算していく
que = [{} for i in range(N+1)]
que[0][0, 0] = 1
for k in range(N):
    cur = que[k]
    nxt = que[k+1]
    for r, g in cur:
        # r < g < b < k+1 の関係を元に次の状態に伝播

        # 制約を満たす場合のみに伝播
        if check(g, k, k+1):
            nxt[g, k] = (nxt.get((g, k), 0) + cur[r, g]) % MOD
        if check(r, k, k+1):
            nxt[r, k] = (nxt.get((r, k), 0) + cur[r, g]) % MOD
        if check(r, g, k+1):
            nxt[r, g] = (nxt.get((r, g), 0) + cur[r, g]) % MOD
print(sum(que[N].values()) % MOD)


Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b(= k) を維持して計算していく
memo = {}
for i in range(N):
    for j in range(i, N):
        # k = N を条件判定するコストが無駄なので事前計算
        memo[i, j, N] = +(r_min[N] <= i <= r_max[N] and g_min[N] <= j <= g_max[N])
def dfs(*key):
    r, g, k = key
    if key in memo:
        return memo[key]
    if not (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k]):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
    res = memo[key] = (dfs(g, k, k+1) + dfs(r, k, k+1) + dfs(r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0))


Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Runtime Error):
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b(= k) を維持して計算していく
memo = {}
for i in range(N):
    for j in range(i+1, N):
        # k = N を条件判定するコストが無駄なので事前計算
        memo[i, j, N] = +(r_min[N] <= i <= r_max[N] and g_min[N] <= j <= g_max[N])
def dfs(*key):
    r, g, k = key
    if key in memo:
        return memo[key]
    if not (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k]):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
    res = memo[key] = (dfs(g, k, k+1) + dfs(r, k, k+1) + dfs(r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0))

Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
from collections import deque
N, M = map(int, input().split())
r_min = [0]*(N+1); r_max = [N+1]*(N+1)
g_min = [0]*(N+1); g_max = [N+1]*(N+1)
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())

    # 仮定: R < G < B を元に各r,gの値の範囲を絞り込む(B = rになるため計算しない)
    if x == 1:
        # x = 1の時、あるrに紐づく全てのl_iについて G < l_i を満たす必要がある
        # => G < min(l_i) を満たせばよい
        g_max[r] = min(g_max[r], l-1)
    elif x == 2:
        # x = 2の時、あるrに紐づく全てのl_iについて R < l_i, l_i <= G を満たす必要がある
        # => R < min(l_i), max(l_i) <= G を満たせばよい
        g_min[r] = max(g_min[r], l)
        r_max[r] = min(r_max[r], l-1)
    elif x == 3:
        # x = 3の時、あるrに紐づく全てのl_iについて l_i <= R を満たす必要がある
        # =>  max(l_i) <= R を満たせばよい
        r_min[r] = max(r_min[r], l)

def check(k, r, g, b):
    return (r_min[k] <= r <= r_max[k] and g_min[k] <= g <= g_max[k])

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    # r < g < b < k+1 なので、この関係を元に次のdfs()を計算
    res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))


Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
from collections import deque
N, M = map(int, input().split())
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())
    C[r].append((l, x))

def check(k, r, g, b):
    # 仮定: r < g < b
    for l, x in C[k]:
        # 区間[l, k]内はx種類の色
        if x == 1:
            if not g < l:
                return 0
        elif x == 2:
            if not r < l or not l <= g:
                return 0
        else:
            if not l <= r:
                return 0
    return 1

MOD = 10**9 + 7

# 左からk個置いた時、各色の最右の位置を持ってメモ化dfs
# r < g < b を維持して計算していく
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    # r < g < b < k+1 の関係を元に次のdfs()を計算
    res = memo[key] = (dfs(k+1, g, b, k+1) + dfs(k+1, r, b, k+1) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

Fixed submission:
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:
                    # 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)

Buggy python submission (verdict: Time Limit Exceeded):
# seishin.py
from collections import deque
N, M = map(int, input().split())
C = [[] for i in range(N+1)]
for i in range(M):
    l, r, x = map(int, input().split())
    C[r].append((l, x))
dp = [[[0]*N for i in range(N)] for j in range(N)]

def check(k, *L):
    # r < g < b として扱う
    r, g, b = sorted(L)
    for l, x in C[k]:
        # 区間[l, k]内はx種類の色
        if x == 1:
            if not g < l:
                return 0
        elif x == 2:
            if not r < l or not l <= g:
                return 0
        else:
            if not l <= r:
                return 0
    return 1

MOD = 10**9 + 7

# 左からk個置いた時の各色の最右の位置を持ってメモ化dfs
memo = {}
def dfs(k, r, g, b):
    key = r, g, b
    if key in memo:
        return memo[key]
    if not check(k, r, g, b):
        # 制約を満たさない場合 => 0通り
        memo[key] = 0
        return 0
    if k == N:
        memo[key] = 1
        return 1
    res = memo[key] = (dfs(k+1, k+1, g, b) + dfs(k+1, r, k+1, b) + dfs(k+1, r, g, k+1)) % MOD
    return res
print(dfs(0, 0, 0, 0))

Fixed submission:
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:
                    # 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)