Problem:


Score: 500 points

Problem Statement

N people are standing in a queue, numbered 1, 2, 3, ..., N from front to back. Each person wears a hat, which is red, blue, or green.

The person numbered i says:

"In front of me, exactly A_i people are wearing hats with the same color as mine."

Assuming that all these statements are correct, find the number of possible combinations of colors of the N people's hats.

Since the count can be enormous, compute it modulo 1000000007.

Constraints

1 \leq N \leq 100000

0 \leq A_i \leq N-1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 A_3 ... A_N

Output

Print the number of possible combinations of colors of the N people's hats, modulo 1000000007.

Sample Input 1

6
0 1 2 3 4 5

Sample Output 1

3

We have three possible combinations, as follows:

Red, Red, Red, Red, Red, Red

Blue, Blue, Blue, Blue, Blue, Blue

Green, Green, Green, Green, Green, Green

Sample Input 2

3
0 0 0

Sample Output 2

6

Sample Input 3

54
0 0 1 0 1 2 1 2 3 2 3 3 4 4 5 4 6 5 7 8 5 6 6 7 7 8 8 9 9 10 10 11 9 12 10 13 14 11 11 12 12 13 13 14 14 15 15 15 16 16 16 17 17 17

Sample Output 3

115295190



Sample input:
6
0 1 2 3 4 5


Sample output:
3

Submission status: Runtime Error

Solution code:
n = int(input())
A=[int(i) for i in input().split()]
MOD = 1000000007
ans = 1
cnt = [0]*n
cnt[0]=3

for i in range(n):
    ans = ans * cnt[A[i]] %MOD
    cnt[A[i]]-=1
    cnt[A[i]+1]+=1
    if ans==0:
        break
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
A=[int(i) for i in input().split()]
MOD = 1000000007
ans = 1
cnt = [0]*n
cnt[0]=3

for i in range(n):
    ans = ans * cnt[A[i]] %MOD
    cnt[A[i]]-=1
    cnt[A[i]+1]+=1

print(ans if not 0 else 0)

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 1000000007
    N, *A = map(int, read().split())
    C = [0] * N
    C[0] = 3
    ans = 1
    for a in A:
        ans = ans * C[a] % MOD
        if ans == 0:
            print(0)
            return
        C[a] -= 1
        C[a + 1] += 1

    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 1000000007
    N, *A = map(int, read().split())
    seq = [-1] * 3
    ans = 1
    for a in A:
        ans = ans * seq.count(a - 1) % MOD
        seq[seq.index(a - 1)] = a

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))

mod = 1000000007
ans = 1
rgb = [0, 0, 0]
for num in a:
    ans = (ans * rgb.count(num)) % mod
    index = rgb.index(num)
    rgb[index] += 1
print(ans)

Submission status: Runtime Error

Solution code:
54
0 0 1 0 1 2 1 2 3 2 3 3 4 4 5 4 6 5 7 8 5 6 6 7 7 8 8 9 9 10 10 11 9 12 10 13 14 11 11 12 12 13 13 14 14 15 15 15 16 16 16 17 17 17

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def cmb(fact, n, r):
    return fact[n] / fact[n-r] / fact[r]

def solve(N, A):
    ret = ModInt(0)
    group = [[] for _ in range(3)]
    for idx, a in enumerate(A):
        if not a:
            for idx, g in enumerate(group):
                if not g:
                    group[idx].append(0)
                    break
        for idx, g in enumerate(group):
            if g and g[-1] == a - 1:
                group[idx].append(a)
                break

    fact = [ModInt(1)]
    for i in range(1, N + 1):
        fact.append(fact[i - 1] * i)

    rest = N
    pattern = 0
    for g in group:
        if not g:
            break
        ret += cmb(fact, rest, g[-1] + 1)
        rest -= g[-1] + 1
        pattern += 1

    return ret * cmb(fact, 3, pattern)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(N, A))

Submission status: Runtime Error

Solution code:

n=int(input())
a=list(map(int,input().split()))

mod=10**9+7
acnt=dict()
acnt[a[0]]=1
t=3
for i in range(1,n):

    if a[i] in acnt:
        acnt[a[i]]+=1
    else:
        acnt[a[i]]=1

    if a[i]!=0:
        if acnt[a[i]-1]==2:
            if acnt[a[i]]==1:
                t=(t*2)%mod
        elif acnt[a[i]-1]==3:
            if acnt[a[i]]==1:
                t=(t*3)%mod
            elif acnt[a[i]]==2:
                t=(t*2)%mod
    else:
        if acnt[0]==2:
            t=(t*2)%mod

#    print("i:",i,"a[i]:",a[i],"acnt[a[i]]:",acnt[a[i]],"t:",t)
                
print(t)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=list(map(int,input().split()))
    cunt=[0]*n
    cunt[0]=3
    ans=1
    mod=10**9+7
    for a in A:
        ans=ans*cunt[a]%mod
        if ans==0:break
        cunt[a+1]+=1
        cunt[a]-=1
    print(ans)
    

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    A=list(map(int,input().split()))
    rgb=[-1,-1,-1]
    ans=1
    mod=10**9+7
    for a in A:
        ans=ans*Counter(rgb)[a-1]%mod
        rgb[rgb.index(a-1)]+=1
    print(ans)
    

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
mod=10**9+7
if A[0]!=0:
    print(0)
    break
L=[1,0,0]
ans=3
for i in range(1,N):
    a=A[i]
    count=0
    add=True
    for j,l in enumerate(L):
        if a==l:
            count+=1
            if add:
                L[j]+=1
                add=False

    ans*=count
    ans%=mod
print(ans)
#print(L)

Submission status: Runtime Error

Solution code:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  mod=pow(10,9)+7
  dp=[0,0,0] # dp[j]:前から順番に見た時の帽子jの数
  ans=1
  for ai in a:
    ans*=dp.count(ai)
    ans%=mod
    dp[dp.index(ai)]+=1
  print(ans)

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

ans = 1
num_color = [-1, -1, -1]
for a in A:
  ans = (ans * num_color.count(a-1)) % MOD
  num_color[num_color.index(a-1)] = a

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
MOD = 1000000007
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = LI()

    # color_number[i][j]: [0, i)でj番目に多い色の人数
    color_number = [[0, 0, 0] for _ in range(N)]
    for i in range(N-1):
        idx = color_number[i].index(A[i])
        for j in range(3):
            if j==idx:
                color_number[i+1][j] = color_number[i][j] + 1
            else:
                color_number[i+1][j] = color_number[i][j]

    ans = 1
    for i in range(N):
        ans *= color_number[i].count(A[i])
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
_, a = open(0)
mod = 10**9+7
c = 1
l = [3] + [0]*10**6

for a in a.split():
  a = int(a)
  c = c * l[a] % mod
  d[a] -= 1
  d[a] += 1
print(c)

Submission status: Runtime Error

Solution code:
_, *a = open(0)
mod = 10**9+7
c = 1
l = [3] + [0]*10**6

for a in a.split():
  a = int(a)
  c = c * l[a] % mod
  d[a] -= 1
  d[a] += 1
print(c)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
MOD=1000000007
hats=[0,0,0]
ans=1
for i in range(n):
    ai=a[i]
    ans=((ans%MOD)*(hats.count(ai)%MOD))%MOD
    hats[hats.index(a[i])]+=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = map(int, read().split())
ans = 1
mod = 10 ** 9 + 7
memo = [0, 0, 0]
for check in a:
    ans *= memo.count(check)
    ans %= mod
    memo[memo.index(check)] += 1
print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))

colors = [0]*3
dp = [0]*n
for i in range(n):
    c = colors.count(A[i])
    dp[i] = c
    colors[colors.index(A[i])] += 1
ans = 1
for x in dp:
    ans = ans*x % MOD
print(ans % MOD)

Submission status: Runtime Error

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)

MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    RGB = [1, 0, 0]
    ans = 1
    for i in range(1, N):
        a = A[i]
        if a == 0:
            j = RGB.index(a)
            RGB[j] += 1

        elif a in RGB:
            print(0)
            return
        else:
            k = RGB.count(a)
            ans *= k
            ans %= MOD
            j = RGB.index(a)
            RGB[j] += 1
    z = RGB.count(0)
    if z == 0:
        ans *= 6
        ans %= MOD
    elif z == 1:
        ans *= 6
        ans %= MOD
    else:
        ans *= 3
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)

MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    RGB = [1, 0, 0]
    ans = 1
    for i in range(1, N):
        a = A[i]
        if a == 0:
            j = RGB.index(a)
            RGB[j] += 1
        else:
            k = RGB.count(a)
            ans *= k
            ans %= MOD
            j = RGB.index(a)
            RGB[j] += 1
    z = RGB.count(0)
    if z == 0:
        ans *= 6
        ans %= MOD
    elif z == 1:
        ans *= 6
        ans %= MOD
    else:
        ans *= 3
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))

    ans = 1
    cnt = [0, 0, 0]
    for a in A:
        i = cnt.index(a)
        c = cnt.count(a)
        cnt[i] += 1
        ans *= c
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
li = list(map(int,input().split()))

xyz = [[0,0,0]for _ in range(n)]
xyz[0] = [0,0,0]

mod = 10**9+7

for i in range(n-1):
    ix = xyz[i].index(li[i])
    if ix > 2:
        print(0)
        exit()
    for j in range(3):
        if j == ix:
            xyz[i+1][j] = xyz[i][j] + 1
        else:
            xyz[i+1][j] = xyz[i][j]

point = 3

for i in range(1,n):
    point *= xyz[i].count(li[i])
    point %= mod
print(point)

Submission status: Runtime Error

Solution code:
n = int(input())
li = list(map(int,input().split()))

xyz = [[0,0,0]for _ in range(n)]
xyz[0] = [0,0,0]

mod = 10**9+7

for i in range(n-1):
    ix = xyz[i].index(li[i])
    for j in range(3):
        if j == ix:
            xyz[i+1][j] = xyz[i][j] + 1
        else:
            xyz[i+1][j] = xyz[i][j]

point = 3
for i in range(1,n):
    point *= xyz[i].count(li[i])
    point %= mod
print(point)

Submission status: Runtime Error

Solution code:
n = int(input())
li = list(map(int,input().split()))

pos = [0]*n
pos[0] = 3

mod = 10**9+7

if li[1]-li[0] == 0:
    pos[1] = 6
else:
    pos[1] = 3

for i in range(2,n):
    #連続3つが違う色
    if li[i]-li[i-2] == 0:
        pos[i] = pos[i-2]*2%mod
    #連続3つが同じ色
    elif li[i]-li[i-2] == 2:
        pos[i] = pos[i-2]
    #二つが同じ色
    else:
        pos[i] = pos[i-2]*4%mod

print(pos[-1])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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