Problem p02845 (python)

Fixed submission:
import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(sys.stdin.readline())
left = list(map(int, sys.stdin.read().split()))
counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    if sum(h) != N:
        return 0
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(sys.stdin.readline())
left = list(map(int, sys.stdin.read().split()))
assert len(left) == N
assert left[0] == 0

counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(sys.stdin.readline())
left = list(map(int, sys.stdin.read()))
assert len(left) == N
assert left[0] == 0

counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
M = 1000000007
N = int(input())
left = list(map(int, input().split()))
assert len(left) == N
assert left[0] == 0

counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    #assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    #assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
M = 1000000007
N = int(input())
left = list(map(int, input().split()))
assert len(left) == N
assert left[0] == 0

counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    #assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h))) % M
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
M = 1000000007
N = int(input())
left = list(map(int, input().split()))
#assert len(left) == N
#assert left[0] == 0

counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    #assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    #assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
import numpy as np
from collections import Counter
import bisect

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
M = 1000000007
N = int(input())
left = list(map(int, input().split()))
assert len(left) == N
assert left[0] == 0

indices = Counter()
for i, x in enumerate(left):
    indices[x] += 1


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = indices.get(i, 0)
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
import numpy as np
from collections import Counter
import bisect

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = Counter()
for i, x in enumerate(left):
    indices[x] += 1


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = indices.get(i, 0)
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
import numpy as np
from collections import Counter
import bisect

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = Counter()
for i, x in enumerate(left):
    indices[x] += 1


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = indices[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
import numpy as np
from collections import Counter
import bisect

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = Counter()
for i, x in enumerate(left):
    indices[x] += 1


def dp(t, n1, n2, n3):
    cached = t.get((n1, n2, n3))
    if cached is not None:
        return cached
    remaining = n1 + n2 + n3
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    if n1 < 200 and n2 < 200 and n3 < 200:
        t[n1, n2, n3] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = indices[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, h[0], h[1], h[2])
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
import numpy as np
from collections import Counter
import bisect

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = Counter()
for i, x in enumerate(left):
    indices[x] += 1


def dp(t, n1, n2, n3):
    cached = t.get((n1, n2, n3))
    if cached is not None:
        return cached
    remaining = n1 + n2 + n3
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = indices[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, h[0], h[1], h[2])
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
from collections import defaultdict
import bisect

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    cached = t.get((n1, n2, n3))
    if cached is not None:
        return cached
    remaining = n1 + n2 + n3
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, h[0], h[1], h[2])
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
import numpy as np
from collections import defaultdict
import bisect

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    cached = t.get((n1, n2, n3))
    if cached is not None:
        return cached
    remaining = n1 + n2 + n3
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, h[0], h[1], h[2])
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
import numpy as np
from collections import defaultdict
import bisect

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    cached = t[n1, n2, n3]
    if cached >= 0:
        return cached
    remaining = n1 + n2 + n3
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    t = -np.ones(shape=(h[0] + 1, h[1] + 1, h[2] + 1), dtype=np.int32)
    t[0, 0, 0] = 1
    res = dp(t, h[0], h[1], h[2])
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
import numpy as np
from collections import defaultdict
import bisect

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, ns):
    n1, n2, n3 = ns
    remaining = n1 + n2 + n3
    if remaining < 0:
        return 0
    cached = t[n1, n2, n3]
    if cached >= 0:
        return cached
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, sorted([n1 - 1, n2, n3]))
        res %= M
    if last_cnt == n2:
        res += dp(t, sorted([n1, n2 - 1, n3]))
        res %= M
    if last_cnt == n3:
        res += dp(t, sorted([n1, n2, n3 - 1]))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    t = -np.ones(shape=(h[0] + 1, h[1] + 1, h[2] + 1), dtype=np.int64)
    t[0, 0, 0] = 1
    res = dp(t, sorted(h))
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
import numpy as np
from collections import defaultdict
import bisect

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    remaining = n1 + n2 + n3
    if remaining < 0:
        return 0
    cached = t[n1, n2, n3]
    if cached >= 0:
        return cached
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    t = -np.ones(shape=(h[0] + 1, h[1] + 1, h[2] + 1), dtype=np.int64)
    t[0, 0, 0] = 1
    res = dp(t, h[0], h[1], h[2])
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
import numpy as np
from collections import defaultdict
import bisect

sys.setrecursionlimit(10 ** 6)
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    remaining = n1 + n2 + n3
    if remaining < 0:
        return 0
    cached = t[n1, n2, n3]
    if cached >= 0:
        return cached
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    t = -np.ones(shape=(h[0] + 1, h[1] + 1, h[2] + 1), dtype=np.int64)
    t[0, 0, 0] = 1
    res = dp(t, h[0], h[1], h[2])
    return res * len(set(itertools.permutations(h))) % M


print(solve())

Buggy submission (verdict: Runtime Error):
import itertools
import sys
import numpy as np
from collections import defaultdict
import bisect

sys.setrecursionlimit(10 ** 6)
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    remaining = n1 + n2 + n3
    if remaining < 0:
        return 0
    cached = t[n1, n2, n3]
    if cached >= 0:
        return cached
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    #print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    heads = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            heads[0] = heads[1] = heads[2] = i + 1
        elif k == 2:
            heads[0] = heads[1] = i + 1
        elif k == 1:
            heads[0] = i + 1
        else:
            break
    res = 0
    for h in set(itertools.permutations(heads)):
        t = -np.ones(shape=(h[0] + 1, h[1] + 1, h[2] + 1), dtype=np.int64)
        t[0, 0, 0] = 1
        res += dp(t, h[0], h[1], h[2])

    return res


print(solve())

Buggy submission (verdict: Runtime Error):
import sys
import numpy as np
from collections import defaultdict
import bisect

sys.setrecursionlimit(10**6)
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    remaining = n1 + n2 + n3
    if remaining < 0:
        return 0
    cached = t[n1, n2, n3]
    if cached >= 0:
        return cached
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    heads = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            heads[0] = heads[1] = heads[2] = i + 1
        elif k == 2:
            heads[0] = heads[1] = i + 1
        elif k == 1:
            heads[0] = i + 1
        else:
            break
    t = -np.ones(shape=(heads[0] + 1, heads[1] + 1, heads[2] + 1), dtype=np.int64)
    t[0, 0, 0] = 1
    num_colors = len(indices[0])
    base = dp(t, heads[0], heads[1], heads[2])
    if len(indices[0]) < 3:
        return 3 * base
    else:
        return base


print(solve())

Buggy submission (verdict: Runtime Error):
import numpy as np
from collections import defaultdict
import bisect

M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    remaining = n1 + n2 + n3
    if remaining < 0:
        return 0
    cached = t[n1, n2, n3]
    if cached >= 0:
        return cached
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    heads = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            heads[0] = heads[1] = heads[2] = i + 1
        elif k == 2:
            heads[0] = heads[1] = i + 1
        elif k == 1:
            heads[0] = i + 1
        else:
            break
    t = -np.ones(shape=(heads[0] + 1, heads[1] + 1, heads[2] + 1), dtype=np.int64)
    t[0, 0, 0] = 1
    num_colors = len(indices[0])
    base = dp(t, heads[0], heads[1], heads[2])
    if len(indices[0]) < 3:
        return 3 * base
    else:
        return base


print(solve())

Buggy submission (verdict: Runtime Error):
import numpy as np
from collections import defaultdict
import bisect

M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    remaining = n1 + n2 + n3
    if remaining < 0:
        return 0
    cached = t[n1][n2][n3]
    if cached is not None:
        return cached
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1][n2][n3] = res
    return res


def solve():
    heads = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            heads[0] = heads[1] = heads[2] = i + 1
        elif k == 2:
            heads[0] = heads[1] = i + 1
        elif k == 1:
            heads[0] = i + 1
        else:
            break
    t = [
        [[None] * (heads[2] + 1) for _ in range(heads[1] + 1)]
        for _ in range(heads[0] + 1)
    ]
    t[0][0][0] = 1
    num_colors = len(indices[0])
    base = dp(t, heads[0], heads[1], heads[2])
    if len(indices[0]) < 3:
        return 3 * base
    else:
        return base


print(solve())