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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import collections
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=2
        b.append(i)

elif a.count(0)==3:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
        b.append(i)

if a.count(collections.Counter(a).most_common()[0][0])>=4:
    ans=0

print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import collections
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=2
        b.append(i)

elif a.count(0)==3:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
        b.append(i)

if a.count(collections.Counter(l).most_common()[0][0])>=4:
    ans=0

print(ans%1000000007)

Submission status: Runtime Error

Solution code:
from statistics import mode
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=2
        b.append(i)

elif a.count(0)==3:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
        b.append(i)

if a.count(mode(a))>=4:
    ans=0

print(ans%1000000007)

Submission status: Runtime Error

Solution code:

from statistics import mode
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=2
        b.append(i)

elif a.count(0)==3:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
        b.append(i)
else:
    ans=0
if a.count(mode(a))>=4:
    ans=0
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    
elif a.count(0)==3:
    ans=6
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=2
        elif i>0 and s-k==1:
            ans*=1
        b.append(i)
    
elif a.count(0)==3:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
        if 1000000007<=ans:
            ans=ans%1000000007
        b.append(i)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
#98
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=3
        elif i>0 and s-k==1:
            ans*=2
        b.append(i)
    
elif a.count(0)==3:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
        b.append(i)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
#98
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=3
        elif i>0 and s-k==1:
            ans*=2
        b.append(i)
    
elif a.count(0)==3:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
            ans*=1
        b.append(i)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
#98
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=3
        elif i>0 and s-k==1:
            ans*=2
        b.append(i)
    
elif a.count(0)==3:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
        elif i>0 and s-k==1:
            ans*=1
        b.append(i)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=[]
if a.count(0)==1:
    ans=3
elif a.count(0)==2:
    ans=2
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==2:
            ans*=2
        elif i>0 and s-k==1:
            ans*=1
        b.append(i)
    
elif a.count(0)==3:
    ans=6
    for i in a:
        k=b.count(i)#その数が何個あるか
        s=b.count(i-1)
        if i>0 and s-k==3:
            ans*=3
        elif i>0 and s-k==2:
            ans*=2
        elif i>0 and s-k==1:
            ans*=1
        b.append(i)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
def color(A, dic):
  if len(A) == 0:
    return 1
  t = A.pop()
  dic[t] -= 1
  return ((3-dic[t])*color(A, dic)) % (10**9 + 7)

n = int(input())
A = list(map(int, input().split()))
dic = {}
for i in range(n):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1
print(color(A, dic))

Submission status: Runtime Error

Solution code:
def color(A, dic):
  if len(A) == 0:
    return 1
  t = A.pop()
  dic[t] -= 1
  return (3-dic[t])*color(A, dic)

n = int(input())
A = list(map(int, input().split()))
dic = {}
for i in range(n):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1
print(color(A, dic))

Submission status: Runtime Error

Solution code:
n=int(input())
A=list(map(int,input().split()))
N=[0]*(10**6)
ans=10**9+7
if len([a for a in A if a==0])==1:
    ans=3
else:
    ans=6

for a in A:
    N[a]+=1
    if a!=0:
        ans*=N[a-1]%mod
        N[a-1]-=1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
# print(A)
RGB = [1,0,0]
M = 10**9+7

c = 3
for i in range(1,N):
    c = (c * RGB.count(A[i]))%M
    RGB[RGB.index(A[i])] += 1
    # print(RGB)
print(c)

Submission status: Runtime Error

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

nums = [0,0,0]
ans = 1
for a in A:
  ans = (ans*nums.count(a))%(10**9 +7)
  nums[nums.index(a)] +=1
print(ans)

Submission status: Runtime Error

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

def f(i, r, b):
    if i == N:
        return 1
    if (i, r, b) in dp:
        return dp[(i, r, b)]
    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == r:
        ans += f(i + 1, r + 1, b)
    if A[i] == b:
        ans += f(i + 1, r, b + 1)
    if A[i] == i - r - b:
        ans += f(i + 1, r, b)

    dp[(i, r, b)] = ans % mod
    return dp[(i, r, b)]

print(f(0, 0, 0) % mod)

Submission status: Runtime Error

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

def f(i, r, b, g):
    if i == N:
        return 1
    if (i, r, b, g) in dp:
        return dp[(i, r, b, g)]
    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == r:
        ans += f(i + 1, r + 1, b, g)
    if A[i] == b:
        ans += f(i + 1, r, b + 1, g)
    if A[i] == g:
        ans += f(i + 1, r, b, g + 1)

    dp[(i, r, b, g)] = ans % mod
    return dp[(i, r, b, g)]

print(f(0, 0, 0, 0) % mod)

Submission status: Runtime Error

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

def f(i, r, b, g):
    if i == N:
        return 1
    if (i, r, b, g) in dp:
        return dp[(i, r, b, g)]
    ans = 0
    # iがr, b, gを被って矛盾がないかを見ていく
    if A[i] == r:
        ans += f(i + 1, r + 1, b, g)
    if A[i] == b:
        ans += f(i + 1, r, b + 1, g)
    if A[i] == g:
        ans += f(i + 1, r, b, g + 1)

    dp[(i, r, b, g)] = ans % mod
    return ans

print(f(0, 0, 0, 0) % mod)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 1000000007
ans = 1
l = []
for i in range(n):
  if a[i] == 0:
    l.append(0)
    ans = ans*(4-len(l))%mod
  else:
    id = 0
    count = 0
    for j in range(len(l)):
      if l[j] == a[i] - 1:
        count += 1
        id = j
    ans = (ans*count)%mod
    l[id] = a[i]
  if ans == 0:
    break
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 1000000007
ans = 1
l = []
for i in range(n):
  if a[i] == 0:
    l.append(0)
    ans = ans*(4-len(l))%mod
  else:
    id = 0
    count = 0
    for j in range(len(l)):
      if l[j] == a[i] - 1:
        count += 1
        id = j
    ans = (ans*count)%mod
    l[id] = a[i]
print(ans)

Submission status: Runtime Error

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

ans = 1
dp = [0]*3
for a in A:
    ans = ans*dp.count(a) % MOD
    dp[dp.index(a)] += 1
print(ans)

Submission status: Runtime Error

Solution code:
input()
v = [0,0,0]
ans = 1
MOD = 1000000007
for a in map(int,input().split()):
    c = v.count(a)
    ans *= c
    ans %= MOD
    v[v.index(a)] += 1
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env pytho3
n = int(input())
a = list(map(int,input().split()))
# ３種類の値をもち、自分より前に同じ色の人がa[i]となる組み合わせ
# コーナーケースとして、全部同じ色なら3通り、あとは*6したらいい
# n<=10**5
# 先頭を色１、次にa[i] == 0になった点を色2,3にしてしていい。前から埋める
# 前から見ていって、それぞれの色の今の人数をcolorとして
# color.count(a[i]) == 2　ならans *= 2, ==3 ans *= 3
mod = 10**9 + 7
if a == list(range(n)): print(3)
else:
  k = 0
  ans = 6
  color = [0,0,0]
  for person in range(n):
    #print(color,person)
    bit = 0#すでにcolor == a[i]が出てきているか?
    if a[person] == 0:
      color[k] = 1
      k += 1
      continue
    for num in range(3):
      if color[num] == a[person]:
        bit += 1
        if bit == 1:
          color[num] += 1
      if num == 2: 
        ans *= bit
        ans = ans % mod
  print(ans)

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy
input = sys.stdin.readline
MOD = 10**9 + 7
LI = lambda : [int(x) for x in input().split()]
N = int(input())
A = LI()
c =[0,0,0]
cnt = [0 for _ in range(N)]
for i in range(N):
    cnt[i] = c.count(A[i])
    c[c.index(A[i])] += 1
ans = 1
for i in range(N):
    ans = (ans * cnt[i]) % MOD
print (ans)

Submission status: Runtime Error

Solution code:
import math
import itertools
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
color = [0]*3
ans = 1
for i in range(N):
  ind = color.index(A[i])
  ans *= len([c for c in color if c == A[i]])
  ans %= mod
  color[ind] += 1

#ans = rec(color,0)
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
D=[0]*3
ans=1
for i in A:
  c=0
  E=[]
  if i==D[0]:
    c+=1
    E.append(0)
  if i==D[1]:
    c+=1
    E.append(1)
  if i==D[2]:
    c+=1
    E.append(2)
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
D=[-1]*3
ans=1
for i in A:
  c=0
  E=[]
  if i-1==D[0]:
    c+=1
    E.append(0)
  if i-1==D[1]:
    c+=1
    E.append(1)
  if i-1==D[2]:
    c+=1
    E.append(2)
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
D=[-1,-1,-1]
ans=1
for i in A:
  c=0
  E=[]
  if i-1==D[0]:
    c+=1
    E.append(0)
  if i-1==D[1]:
    c+=1
    E.append(1)
  if i-1==D[2]:
    c+=1
    E.append(2)
  D[E[0]]+=1
  ans*=c
  ans%=10**9+7
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
rbg = [-1, -1, -1]
ans = 1
mod = 10 ** 9 + 7

for A in a:
    ans *= rbg.count(A - 1)
    ans %= mod
    rbg[rbg.index(A - 1)] = A

print(ans)

Submission status: Runtime Error

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

def count(n, list1):
    num0 = list1.count(0)
    if num0 == 2 or num0 == 3:
        statuslist = []
        answer = 1
        for i in range(len(list1)):
            if list1[i] == 0:
                statuslist.append(0)
            else:
                pos = statuslist.count(list1[i]-1)
                answer *= pos
                statuslist.remove(list1[i]-1)
                statuslist.append(list1[i])
        answer *= 6
        return (answer % 1000000007)
    else:
        return 3
        

print(count(n, list1))

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

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

ret = 1
cnt = [0] * n
zero = 0
for x in a:
    if x:
        ret = ret * cnt[x - 1] % mod
        cnt[x - 1] -= 1
    else:
        zero += 1
    cnt[x] += 1

if zero == 1:
    ret = ret * 3 % mod
elif 2 <= zero <= 3:
    ret = ret * 6 % mod
else:
    raise ValueError

print(ret)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.buffer.readline
n = int(readline())
A = map(int, readline().split())
mod = 1000000007

caps = [0] * 3
ans = 1
for a in A:
    ans *= caps.count(a)
    caps[caps.index(a)] += 1
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(int)

ans=1
for num in a:
    if num==0:
        ans*= (3 - d[0])
    else:
        ans*= (d[num-1] - d[num])

    ans*=tmp
    ans%=1000000007
    d[num]+=1

print(ans)

Submission status: Runtime Error

Solution code:
M = 1000000007
N = int(input())
A = list(map(int, input().split()))

ans = 1
rgb = [0, 0, 0]
for i in range(N):
    c = rgb.count(A[i])
    p = rgb.index(A[i])
    ans *= c
    rgb[p] += 1

print(ans % M)

Submission status: Runtime Error

Solution code:
MOD=10**9+7
N=int(input())
A=list(map(int, input().split()))
huts=[0]*3
out=1
for i in range(N):
  out*=huts.count(A[i])
  huts[huts.index(A[i])]+=1
print(out%MOD)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    RGB = [-1, -1, -1]
    ans = 1
    for a in A:
        mi = None
        count = 0
        for i in range(3):
            if RGB[i] == a-1:
                if mi == None:
                    RGB[mi] = a
                    mi = i
                count += 1
        if count > 1:
            ans *= count
            ans %= MOD
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    RGB = [-1, -1, -1]
    ans = 1
    for a in A:
        mi = None
        count = 0
        for i in range(3):
            if RGB[i] == a-1:
                if mi == None:
                    mi = i
                count += 1
        ans *= count
        ans %= MOD
        RGB[mi] = a
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
cnt = 1
cnt0 =0
C = {0:0}
B = []
for i in range(N):
    a = A[i]
    if a==0:
        cnt = (cnt*(3-cnt0))%p
        cnt0 += 1
    else:
        cnt = (cnt*C[a-1])%p
        C[a-1] -= 1
    if a not in C:
        C[a] = 0
    C[a] += 1
print(cnt)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
B[0]=3

c=1
for a in A:
    c*=B[a]
    c%=1000000007
    B[a]-=1
    B[a+1]+=1

print(c)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = LI()


ans = 1
color = [0, 0, 0]
for i in range(n):
    ans = ans * color.count(A[i]) % mod
    color[color.index(A[i])] += 1



print(ans)