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


fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


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)

Submission status: Runtime Error

Solution code:
import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N = inputInt()
    A = inputIntList()

    pattern = [0] * N
    pattern[0] = 3

    ret = 1
    for a in A:
        ret *= pattern[a]
        pattern[a] -= 1
        pattern[a + 1] += 1
        # print(pattern)
    return ret


if __name__ == "__main__":
    print(main())

Submission status: Runtime Error

Solution code:
import math


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N = inputInt()
    A = inputIntList()

    pattern = [0] * 4
    pattern[0] = 3

    ret = 1
    for a in A:
        ret *= pattern[a]
        pattern[a] -= 1

        pattern[a + 1] += 1
        # print(pattern)
    return ret


if __name__ == "__main__":
    print(main())

Submission status: Runtime Error

Solution code:
def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def next_state(c, a, n_patterns):
    # c := c[0] >= c[1] >= c[2]
    idx = c.index(a)
    n_equals = 1
    n_equals += 1 if c[idx%3] == c[(idx + 1) % 3] else 0
    n_equals += 1 if c[idx%3] == c[(idx + 2) % 3] else 0
    c[idx%3] += 1
    n_patterns *= n_equals
    n_patterns %= 1000000007
    return c, n_patterns

def solve(N, A):
    c = [0, 0, 0]
    n = 1
    for a in A:
        c, n = next_state(c, a, n)
    return n
    
if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print("%d" % output)

Submission status: Runtime Error

Solution code:
def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def next_state(c, a, n_patterns):
    # c := c[0] >= c[1] >= c[2]
    idx = c.index(a)
    n_equals = 1
    n_equals += 1 if c[idx] == c[(idx + 1) % 3] else 0
    n_equals += 1 if c[idx] == c[(idx + 2) % 3] else 0
    c[idx] += 1
    n_patterns *= n_equals
    n_patterns %= 1000000007
    return c, n_patterns

def solve(N, A):
    c = [0, 0, 0]
    n = 1
    for a in A:
        c, n = next_state(c, a, n)
    return n
    
if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print("%d" % output)

Submission status: Runtime Error

Solution code:
N = int(input())
lst = [int(i) for i in input().split()]
mod = 1000000007
count = [0] * N
count[0] = 3

ret = 1
for i in lst:
    count[i + 1] += 1
    ret = (ret * count[i]) % mod
    count[i] -= 1

print(ret)

Submission status: Runtime Error

Solution code:
=int(input())
A=list(map(int,input().split()))
x=0
y=0
z=0
ans=1
for a in A:
    c=0
    X,Y,Z=x,y,z
    if a==x:
        x+=1
        c+=1
    if a==y:
        c+=1
        if a!=X:
            y+=1
    if a==z:
        c+=1
        if a!=X and a!=Y:
            z+=1
    ans=ans*c%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = map(int, input().split())
xyz,T = [0,0,0],1
for Ai in A:
  n_Ai = xyz.count(Ai)
  T = (T*n_Ai))%1000000007
  if n_Ai>0: xyz.count(Ai)xyz[xyz.index(Ai)] += 1
print(T)

Submission status: Runtime Error

Solution code:
N = int(input())
A = map(int, input().split())
xyz = [0,0,0]
T = 1
for Ai in A:
  T = (T*xyz.count(Ai))%1000000007
  xyz[xyz.index(Ai)] += 1
print(T)

Submission status: Runtime Error

Solution code:
N = int(input())
A = map(int, input().split())
xyz,T = [0,0,0],1
for Ai in A:
  T = (T*xyz.count(Ai))%1000000007
  xyz[xyz.index(Ai)] += 1
print(T)

Submission status: Runtime Error

Solution code:
mod = 1000000007

def mul(x, y):
    return x * y % mod

def f(n, arr):
    answer = 1
    count = [0 for _ in range(n)]
    count[0] = 3
    for e in range(n):
        answer = mul(answer, count[arr[e] - 1] - count[arr[e]])
        count[arr[e]] = count[arr[e]] + 1
        # print("answer ", answer)
    return answer

if __name__ == "__main__":
    n = int(input())
    arr = list(map(int, input().split(' ')))
    for i in range(n):
        arr[i] = arr[i] + 1 
    print(f(n, arr))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
def hats(m):
    if m == 1:
        return 3
    else:
        xL = [i for i, j in enumerate(a) if j == a[m - 1]]
        xS = [i for i, j in enumerate(a) if j == a[m - 1] - 1]
        xl = 0
        xs = 0
        for i in range(len(xL)):
            if xL[i] < m - 1:
                xl += 1
        for i in range(len(xS)):
            if xS[i] < m - 1:
                xs += 1
        if xl + 1 == xs:
            return hats(m - 1) % 1000000007
        else:
            return hats(m - 1) * (xs - xl) % 1000000007
print(hats(n))

Submission status: Runtime Error

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

def hats(m):
    if m == 1:
        return 3
    else:
        xL = [i for i, j in enumerate(a) if j == a[m - 1]]
        xS = [i for i, j in enumerate(a) if j == a[m - 1] - 1]
        xl = 0
        xs = 0
        for i in range(len(xL)):
            if xL[i] < m - 1:
                xl += 1
        for i in range(len(xS)):
            if xS[i] < m - 1:
                xs += 1
        if xl + 1 == xs:
            return hats(m - 1)
        else:
            return hats(m - 1) * (xs - xl)
print(hats(n) % 1000000007)

Submission status: Runtime Error

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

mod = int(1e+9 + 7)
L = [0, 0, 0]
pi = 1
for i in range(N):
  j = 0
  while L[j] != A[i]:
    j += 1
  n = 0
  for k in range(3):
    if L[k] == A[i]:
      n += 1
  if j != 3:
    L[j] += 1
  pi *= n
  pi %= mod
print(pi)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=[0]*n
c[0]=3
cnt=1
for i in a:
  cnt=cnt*c[i]%1000000007
  c[i]-=1
  c[i+1]+=1

print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=[0]*n
c[0]=3
cnt=1
for i in a:
  cnt*=c[i]
  c[i]-=1
  c[i+1]+=1

print(cnt%1000000007)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
H = [0] * 3
P = 1
for i in A:
	P *= H.count(i)
	P %= 1000000007
	H[H.index(i)] += 1
print(P)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
H = [0] * 3
P = 1
for i in A:
	P *= H.count(i)
	H[H.index(i)] += 1
print(P % 1000000007)

Submission status: Runtime Error

Solution code:
n = int(input()) #長さ
a = str(input().split()) #帽子の数
x = 0
y = 0
z = 0
ans = 1
 
for i in range(n): #1文字目
  if a[i] == str(x):
    if x == y & x == z:
      ans = ans * 3
    elif x == y:
      ans = ans * 2
   	x = x + 1
  elif a[i] == str(y):
    if y == z:
      ans = ans * 2
    y = y + 1
  else:
    z = z + 1
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
n = int(input()) #長さ
a = input().split() #帽子の数
x = 0
y = 0
z = 0
ans = 1
 
for i in range(n): #1文字目
  if a[i] == x:
    if x == y & x == z:
      ans = ans * 3
    elif x == y:
      ans = ans * 2
   	x = x + 1
  elif a[i] == y:
    if y == z:
      ans = ans * 2
    y = y + 1
  else:
    z = z + 1
print(ans % 1000000007)

Submission status: Runtime Error

Solution code:
n = int(input()) #長さ
a = map(int, input().split()) #帽子の数
x = 0
y = 0
z = 0
ans = 1

for i in range(n): #1文字目
  if a[i] == x:
    if x == y & x == z:
      ans = ans * 3
    elif x == y:
      ans = ans * 2
    x = x + 1
  elif a[i] == y:
    if y == z:
      ans = ans * 2
    y = y + 1
  else:
    z = z + 1
print(ans % 1000000007)

Submission status: Runtime Error

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

c = [0]*3

a = 1

for i in A:
    a *= c.count(i)
    c[c.index(i)] += 1
    
print(a%1000000007)

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n,*a=map(int,read().split())
	
	aa=max(a)
	
	li=[[] for _ in range(aa+1)]
	
	for i in range(n):
		li[a[i]].append(i)
	
	if len(li[0])>3:
		print(0)
		exit(0)
	else:
		ans=3 if len(li[0])==1 else 6

	for i in range(1,aa+1):
		if len(li[i])>3:
			print(0)
			exit(0)
		else:
			k=bisect.bisect_right(li[i-1],li[i][0])
			ans*=k
			ans%=MOD
			
			if len(li[i])>1:
				k=bisect.bisect_right(li[i-1],li[i][1])-1
				ans *= k
				ans %= MOD
		
	print(ans)
	
	
if __name__ == "__main__":
		main()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n,*a=map(int,read().split())
	
	aa=max(a)
	
	li=[[] for _ in range(aa+1)]
	
	for i in range(n):
		li[a[i]].append(i)
	
	if len(li[0])>3:
		print(0)
		exit(0)
	else:
		ans=3 if len(li[0])==1 else 6

	for i in range(1,aa+1):
		if len(li[i])>3:
			print(0)
			exit(0)
		else:
			k=bisect.bisect_left(li[i-1],li[i][0])
			ans*=k
			ans%=MOD
			
			if len(li[i])>1:
				k=bisect.bisect_left(li[i-1],li[i][1])-1
				ans *= k
				ans %= MOD
		
	print(ans)
	
	
if __name__ == "__main__":
		main()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n,*a=map(int,read().split())
	
	aa=max(a)
	
	li=[[] for _ in range(aa+1)]
	
	for i in range(n):
		li[a[i]].append(i)
	
	ans=3 if len(li[0])==1 else 6
	
	
	
	for i in range(1,aa+1):
		k=bisect.bisect_left(li[i-1],li[i][0])
		ans*=k
		ans%=MOD
		
		if len(li[i])>1:
			k=bisect.bisect_left(li[i-1],li[i][1])-1
			ans *= k
			ans %= MOD
		
	print(ans)
	
	
if __name__ == "__main__":
		main()

Submission status: Runtime Error

Solution code:
N = int(input())

num_list = list(map(int, input().split()))

hats = [0, 0, 0]


ans = 1

for i in range(N):
    same_color = num_list[i]
    cand_num = hats.count(same_color)
    ans *= cand_num
    ans = ans % 1000000007
    hats[hats.index(same_color)] += 1

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
*A, = map(int,input().split())

mod = 10**9+7

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

Submission status: Runtime Error

Solution code:
import collections

n=int(input())
b=[[0,0,0]]
a=[int(i) for i in input().split()]

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

for i in range(n):
    k=b[-1].my_index(a[i])
    if k==-1:
        print(0)
        break
    c=[]
    for j in range(3):
        if j==k:
            c.append(b[-1][j]+1)
        else:
            c.append(b[-1][j])
    b.append(c)
else:
    x=1
    for i in range(n):
        x=x*b[i].count(a[i])%1000000007
    print(x)

Submission status: Runtime Error

Solution code:
import collections

n=int(input())
b=[[0,0,0]]
a=[int(i) for i in input().split()]

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

for i in range(n):
    k=b[-1].index(a[i])
    if k==-1:
        print(0)
        break
    c=[]
    for j in range(3):
        if j==k:
            c.append(b[-1][j]+1)
        else:
            c.append(b[-1][j])
    b.append(c)
else:
    x=1
    for i in range(n):
        x=x*b[i].count(a[i])%1000000007
    print(x)

Submission status: Runtime Error

Solution code:
import collections

n=int(input())
b=[[0,0,0]]
a=[int(i) for i in input().split()]
for i in range(n):
    k=b[-1].index(a[i])
    c=[]
    for j in range(3):
        if j==k:
            c.append(b[-1][j]+1)
        else:
            c.append(b[-1][j])
    b.append(c)
#print(b)
x=1
for i in range(n):
    an=b[i].count(a[i])
    if an==0:
        break
    x=x*an
    x=x%1000000007

print(x)

Submission status: Runtime Error

Solution code:
import collections

n=int(input())
b=[[0,0,0]]
a=[int(i) for i in input().split()]
for i in range(n):
    k=b[-1].index(a[i])
    c=[]
    for j in range(3):
        if j==k:
            c.append(b[-1][j]+1)
        else:
            c.append(b[-1][j])
    b.append(c)
#print(b)
x=1
for i in range(n):
    x=x*b[i].count(a[i])%1000000007

print(x)

Submission status: Runtime Error

Solution code:
		def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    zero = 3
    ans = 1
    ls = [0 for _ in range(N)]
    mod = 1000000007
    for i in A:
        if i == 0:
            ans = (ans*zero)%mod
            zero -= 1
            ls[i] += 1
        else:
            ans = (ans*(ls[i-1]-ls[i]))%mod
            ls[i] +=1

    print(ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
c = [-1,-1,-1]
a = 1
for i in map(int,input().split()):
  a = a * c.count(i-1) % 1000000007
  c[c.index(i-1)] = i
print(a)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
C = [0] * 100000
C[0] = 3
答 = 1
for x in A:
  答 *= C[x]
  答 %= MOD
  C[x] -= 1
  C[x+1] += 1
print(答)

Submission status: Runtime Error

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

col_lst = [0 , 0 , 0]
ans = 1

for i in range(n):
    tmp = lst[i]
    val = col_lst.count(tmp)
    ans = (ans * val) % mod
    col_lst[col_lst.index(tmp)] += 1
print(ans % mod)

Submission status: Runtime Error

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

col_lst = [0 , 0 , 0]
ans = 1

for i in range(n):
    tmp = lst[i]
    val = col_lst.count(tmp)
    ans = ans * val % mod
    col_lst[col_lst.index(tmp)] += 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
color = [0] * 3 # 赤色・青色・緑色の帽子を被っている人数
answer = 1 
MOD = 10 ** 9 + 7

for a in A:
    answer *= color.count(a)
    # aと同じ人数が複数ある場合は一番左の色としてカウント
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = list(map(int, input().split()))
color = [0] * 3 # 赤色・青色・緑色の帽子を被っている人数
answer = 1 
MOD = 10 ** 9 + 7

for a in A:
    answer *= color.count(a)
    # aと同じ人数が複数ある場合は一番左の色としてカウント
    i = color.index(a)
    color[i] += 1
    answer %= MOD

print(answer)

Submission status: Runtime Error

Solution code:
_,a=open(0)
c=1
d=[3]+[0]*10**6
for a in map(int,a.split()):
  c=c*dp[a]%(10**9+7)
  d[a]-=1
  d[a]+=1
print(c)

Submission status: Runtime Error

Solution code:
N=int(input())
a=list(map(int,input().split()))
ans=1
l=[0,0,0]
mod=10**9+7
for i in range(N):
  ans*=(l.count(a[i]))
  index=l.index(a[i])
  l[index]+=1
print(ans%mod)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
x=[0,0,0]
count=1
mod=10**9+7
for i in range(n):
  if x[0]==0 and a[i]==0:
    x[0]+=1
    count=count*3
  elif x[1]==0 and a[i]==0:
    x[1]+=1
    count=count*2
  elif x[2]==0 and a[i]==0:
    x[2]+=1
    count=count*1
  else:
    count=count*x.count(a[i])
    x[x.index(a[i])]+=1
print(count%mod)

Submission status: Runtime Error

Solution code:
N = int(input)
A = list(map(int, input().split()))
L = [0 for i in range(max(A)+2)]
ans = 1
L[0] = 3
p = 10 ** 9 + 7
for i in range(N):
  ai = A[i]
  ans *= (L[ai] - L[ai + 1])
  ans = ans % p
  L[ai + 1] += 1
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=map(int,input().split())
m=10**9+7
r=1
C=[0,0,0]
for a in A:
  i=C.index(a)
  r=r*sum([1 if c==a else 0 for c in C])%m
  C[i]+=1
print(r)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
x=[0,0,0]
count=1
for i in range(n):
  if x[0]==0 and a[i]==0:
    x[0]+=1
    count*=3
  elif x[1]==0 and a[i]==0:
    x[1]+=1
    count*=2
  elif x[2]==0 and a[i]==0:
    x[2]+=1
    count*=1
  else:
    count*=x.count(a[i])
    x[x.index(a[i])]+=1
print(count%(10**9+7))

Submission status: Runtime Error

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

mod=10**9+7
ans=1
cs=[0]*3
for a in A:
  c=cs.count(a)
  ans=(ans*c)%mod
  i=cs.index(a)
  cs[i]+=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from bisect import *
import math

input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
mod = 1000000007

cnum = A.count(0)
amax = max(A)

numind = [[] for i in range(amax+1)]
for i,ai in enumerate(A):
	numind[ai].append(i)

if cnum==0:
	res = 0
else:
	res = 1
	for i in range(amax):
		if len(numind[i+1])==0:
			res = 0
			break
		for order, j in enumerate(numind[i+1]):
			res = (res * (bisect(numind[i],j)-order)) % mod

	res = (res*math.factorial(3)//math.factorial(3-cnum)) % mod

print(res)

Submission status: Runtime Error

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

T = 1
xyz = [0]*3
for Ai in A:
  T = (T * sum([i==Ai for i in xyz]))%1000000007
  xyz[xyz.index(Ai)] += 1
print(T)

Submission status: Runtime Error

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32

def solve(A, N):
    MOD = 1000000007
    x = 0
    y = 0
    z = 0
    count = 1
    for i in range(N):
        if A[i] == x:
            if x == y and x == z:
                count = (count * 3) % MOD
            elif x == y:
                count = (count * 2) % MOD
            x += 1
        elif A[i] == y:
            if y == z:
                count = (count * 2) % MOD
            y += 1
        elif A[i] == z:
            z += 1
        else:
            A[N] = 1
    return count

def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    A = np.empty(N, i8)
    for i, c in enumerate(map(int, stdin.readline().split())):
        A[i] = c
    print(solve(A, N))

main2()

Submission status: Runtime Error

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

T = 1
xyz = [0]*3
for Ai in A:
  T = ((T%1000000007) * (sum([i==Ai for i in xyz])%1000000007))%1000000007
  xyz[xyz.index(Ai)] += 1
print(T)

Submission status: Runtime Error

Solution code:

INF = 1000000007
N = int(input())
A = list(map(int, input().split()))
blst =[0, 0, 0]
blst[0] += 1
ans = 3
for i in range(1, N):
    cnt = blst.count(A[i])
    ans *= cnt
    ans %= INF
    index = blst.index(A[i])
    blst[index] += 1
    if ans == 0:
        ans = 0
        break

print(ans)

Submission status: Runtime Error

Solution code:

INF = 1000000007
N = int(input())
A = list(map(int, input().split()))
blst =[0, 0, 0]
blst[0] += 1
ans = 3
for i in range(1, N):
    cnt = blst.count(A[i])
    ans *= cnt
    ans %= INF
    index = blst.index(A[i])
    blst[index] += 1

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A = list(map(int,input().split()))
lis = [0]*200000
ans=1
num_zero=0
mod = 1000000007
for i in A:
  lis[i]+=1
  if i!=0:
    ans*=lis[i-1]
    lis[i-1]-=1
    ans%=mod
    if lis[i-1]<0:
      ans=0
      break
    
  else:
    num_zero+=1

if num_zero>=2:
  mul = 6
  
elif num_zero = 0:
  mul = 0

else:
  mul = 3
  
print((ans*mul)%mod)

Submission status: Runtime Error

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

c = [-1, -1 ,-1]

sum = 1
tmp = 0
for a in A:
    sum = sum * c.count(A-1) % 1000000007
    if A-1 == c[0]:
        c[0] += 1
        tmp = c.count(c[0] - 1) + 1
    elif A-1 == c[1]:
        c[1] += 1
        tmp = c.count(c[1]-1) + 1
    elif A-1 == c[2]:
        c[2] += 1
        tmp = c.count(c[2] - 1) + 1
print(sum)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
mod = float(1000000007)
C = [1,0,0]
j = 1
ans = float(3)
for i in range(1,N):
    if A[i] == 0:
        C[j] = 1
        ans = (ans * (3-j)) % mod
        j += 1
    else:
        if C[0] == C[1] and C[1] == C[2]:
            C[0] += 1
            ans = (ans * 3) % mod
        elif C[0] == C[1] and A[i] == C[0]:
            ans = (ans * 2) % mod
            C[0] += 1
        elif C[1] == C[2] and A[i] == C[1]:
            C[1] += 1
            ans = (ans * 2) % mod
        else:
            for k in range(3):
                if A[i] == C[k]:
                    C[k] += 1
print(int(ans))

Submission status: Runtime Error

Solution code:
n = int(input())

hats = [0, 0, 0]
count = 1
mod = 1000000007

for a in map(int, input().split()):
  count *= hats.count(a)
  count %= mod
  hats[hats.index(a)] += 1
  
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())

hats = [0, 0, 0]
count = 1
mod = 1000000007

for a in map(int, input().split()):
  count *= hats.count(a)
  count %= mod
  count[count.index(a)] += 1
  
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
m = 10**9+7
ans = 1
rgb = [0,0,0]
for i in range(n):
    cnt = 1
    for j in range(3):
        if a[i] == rgb[j]:
            cnt += 1
    if cnt != 1:
        cnt -= 1
    ans *= cnt
    if a[i] == 0 and 0 in rgb:
        rgb[rgb.index(0)] += 1
    else:
        rgb[rgb.index(a[i])] += 1
cnt = 1
for i in range(3):
    if a[-1] == rgb[i]:
        cnt += 1
if cnt != 1:
    cnt -= 1
ans *= cnt
print(ans%m)

Submission status: Runtime Error

Solution code:
import math
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
    
p = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
imax = a[n-1]

for i in range(imax):
    if a.count(i) == 3:
        continue
    else:
        imin = i
        break
imid = n - imax - imin -1

anus = math.factorial(imax)%p
pussy = math.factorial(imid)%p
oral = math.factorial(imin)%p

print(((math.factorial(n)%p)*power_func(anus,p-2,p)*power_func(pussy,p-2,p)*power_func(oral,p-2,p))*3%p)
print(imax,imid,imin)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N = int(input())
*A, = map(int, input().split())
hats = [0] * 3
ans = 1
for a in A:
    ans = (ans * len([h for h in hats if h == a])) % MOD
    idx = hats.index(a)
    hats[idx] += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from bisect import *
import math

input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
mod = 1000000007

cnum = A.count(0)
if cnum==0:
	res = 0
else:
	amax = max(A)
	numind = [[] for i in range(amax+1)]
	for i,ai in enumerate(A):
		numind[ai].append(i)

	res = 1
	for i in range(amax):
		for order, j in enumerate(numind[i+1]):
			res = (res * (bisect(numind[i],j)-order)) % mod

	res = (res*math.factorial(3)//math.factorial(3-cnum)) % mod

print(res)

Submission status: Runtime Error

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

c = [0, 0, 0]

sum = 1
# print(c)
for a in A:
    # print(a)
    if a == c[0]:
        c[0] += 1
        tmp = c.count(c[0] - 1) + 1
    elif a == c[1]:
        c[1] += 1
        tmp = c.count(c[1]-1) + 1
    elif a == c[2]:
        c[2] += 1
        tmp = c.count(c[2] - 1) + 1
    # print(tmp)
    sum = sum * tmp % 1000000007
    # print(c)
print(sum)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split())
r = {}
total = 1
for i in range(N):
  if A[i] in r.keys():
    r[A[i]] += 1
  else:
    r[A[i]] = 1
  if A[i] == 0:
    total = total * (4-r[A[i]])
  else:
    total = total * (r[A[i] - 1] - r[A[i]] + 1)
total = total % (10 ** 9 + 7)
print(total)

Submission status: Runtime Error

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

mod=1000000007
ans=1
r,b,g=0,0,0
for i in a:
    if r2==r and b2==b and g2==g:
        print(0)
        exit()
    if i==r and i==b and i==g:
        ans*=3
        ans%=mod
        r+=1
    elif (i==r and i==b) or (i==g and i==r):
        ans*=2
        ans%=mod
        r+=1
    elif i==b and i==g:
        ans*=2
        ans%=mod
        g+=1
    elif i==r:
        r+=1
    elif i==b:
        b+=1
    elif i==g:
        g+=1

    else:
        print(0)
        exit()
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = rl()
color = [0] * 3
answer = 1
MOD = 10 ** 9 + 7

for a in A:
    answer = answer * color.count(a) % MOD
    i = color.index(a)
    color[i] += 1
    if answer == 0:
        break

print(answer)

Submission status: Runtime Error

Solution code:
import sys
from bisect import *
import math

input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
mod = 1000000007

cnum = A.count(0)
amax = max(A)

numind = [[] for i in range(amax+1)]
for i,ai in enumerate(A):
	numind[ai].append(i)

res = 1
for i in range(amax):
	for order, j in enumerate(numind[i+1]):
		res = (res * (bisect(numind[i],j)-order)) % mod

res = (res*math.factorial(3)//math.factorial(3-cnum)) % mod

print(res)

Submission status: Runtime Error

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

# print(A)
c = [0, 0, 0]
# r = 0
# b = 0
# g = 0
sum = 1
# print(c)
for a in A:
    a = int(a)
    # print(a)
    if a == c[0]:
        c[0] += 1
        tmp = c.count(c[0] - 1) + 1
    elif a == c[1]:
        c[1] += 1
        tmp = c.count(c[1]-1) + 1
    elif a == c[2]:
        c[2] += 1
        tmp = c.count(c[2] - 1) + 1
    # print(tmp)
    sum *= tmp
    # print(c)
print(sum % 1000000007)

Submission status: Runtime Error

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

# print(A)
c = [0, 0, 0]
# r = 0
# b = 0
# g = 0
sum = 1
# print(c)
for a in A:
    # print(a)
    if a == c[0]:
        c[0] += 1
        tmp = c.count(c[0] - 1) + 1
    elif a == c[1]:
        c[1] += 1
        tmp = c.count(c[1]-1) + 1
    elif a == c[2]:
        c[2] += 1
        tmp = c.count(c[2] - 1) + 1
    # print(tmp)
    sum *= tmp
    # print(c)
print(sum % 1000000007)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split())
r = {}
total = 1
for i in range(N):
  if A[i] in r.keys:
    r[A[i]] += 1
  else:
    r[A[i]] = 1
  if A[i] == 0:
    total = total * (4-r[A[i]])
  else:
    total = total * (r[A[i] - 1] - r[A[i]] + 1)
total = total % (1000000007)
print(total)

Submission status: Runtime Error

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

# print(A)
c = [0, 0, 0]
# r = 0
# b = 0
# g = 0
sum = 1
# print(c)
for a in A:
    # print(a)
    if a == c[0]:
        c[0] += 1
        tmp = c.count(c[0] - 1) + 1
    elif a == c[1]:
        c[1] += 1
        tmp = c.count(c[1]-1) + 1
    elif a == c[2]:
        c[2] += 1
        tmp = c.count(c[2] - 1) + 1
    # print(tmp)
    sum *= tmp
    # print(c)
print(sum)