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: Accepted

Solution code:
mod=1000000007

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

ans=1
c1=c2=c3=0
for Ai in A:
    if c1==c2==c3==Ai:
        c1+=1
        ans=ans*3%mod
    elif c1==c2==Ai:
        c1+=1
        ans=ans*2%mod
    elif c2==c3==Ai:
        c2+=1
        ans=ans*2%mod
    elif c1==Ai:
        c1+=1
    elif c2==Ai:
        c2+=1
    elif c3==Ai:
        c3+=1
    else:
        ans=0
        break

print(ans)

Submission status: Accepted

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

dp = [(1, [0, 0, 0])]
for i in range(N):
    p = dp[i][0]

    cc = 0
    sw = False
    cp = [dp[i][1][0], dp[i][1][1], dp[i][1][2]]
    for c in range(3):
        if As[i] == dp[i][1][c]:
            cc += 1
            if not sw:
                cp[c] += 1
                sw = True
    p = (p * cc) % E
    dp.append((p, cp))
print(dp[N][0])

Submission status: Accepted

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 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: Accepted

Solution code:
#入力
N=int(input())
A = [int(x) for x in input().split()]

ans = [0]*3
answer=1
for i in range(N):
    count=0
    if (A[i] == ans[0]):
        count+=1
    if (A[i] == ans[1]):
        count+=1
    if (A[i] == ans[2]):
        count+=1
    answer*=count
    answer %= 1000000007

    if(A[i] == ans[0]):
        ans[0]+=1
    elif(A[i] == ans[1]):
        ans[1]+=1
    elif(A[i] == ans[2]):
        ans[2]+=1

print(answer)

Submission status: Accepted

Solution code:
n=int(input())
d=[-1,-1,-1]
x=1
for i in list(map(int,input().split())):
  x*=d.count(i-1)
  x%=10**9+7
  if i-1 in d:d[d.index(i-1)]+=1
print(x)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
sosu = 10 ** 9 + 7
dp = [0 for i in range(N)]
ans = 1
for i in range(N):
    if A[i] >= 1:
        nnn = dp[A[i]-1] - dp[A[i]]
    else:
        nnn = 3 - dp[A[i]]
    if nnn > 0:
        ans *= nnn
    elif nnn <= 0:
        ans *= 0
    ans = ans % sosu
    dp[A[i]] += 1
#print(dp)
print(ans)

Submission status: Accepted

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


def main():
    MOD = 1000000007
    N = int(input())
    A = [int(x) for x in input().split()]

    ans = 1
    red = 0
    blue = 0
    green = 0

    for i in range(N):
        count = 0
        if red == A[i]:
            count += 1
        if blue == A[i]:
            count += 1
        if green == A[i]:
            count += 1

        if red == A[i]:
            red += 1
        elif blue == A[i]:
            blue += 1
        elif green == A[i]:
            green += 1

        ans = ans * count

    print(ans % MOD)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

mod = 10**9+7
ans = 1

num = [0]*(n+1)
num[0] = 3

for i in range(0,n):
    if i < a[i]:
        print(0)
        exit()
    ans *= num[a[i]]
    ans %= mod
    num[a[i]] -= 1
    num[a[i]+1] += 1
    #print(ans)
        
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())

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

ans = 1
d = defaultdict(int)

for i,n in enumerate(A):
    if n == 0:
        ans *= (3-d[n])
        d[n] += 1
    else:
        ans *= (d[n-1] - d[n])
        d[n] += 1

print(ans % (10**9+7))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
d = [-1, -1, -1]
ans = 1
P = 10**9+7
for n in range(N):
    ans = ans*d.count(A[n]-1)%P
    if d[0] == A[n]-1:
        d[0] += 1
    elif d[1] == A[n]-1:
        d[1] += 1
    else:
        d[2] += 1
print(ans)

Submission status: Accepted

Solution code:
INF = int(1e9) + 7

n = int(input())
a = list(map(int, input().split()))
col = [0, 0, 0]
ans = 1
for i in range(n):
    m = 0
    for j in range(3):
        if a[i] ==col[j]:
            m = col.count(a[i])
    ans *= m
    
    for j in range(3):
        if a[i]==col[j]:
            col[j] +=1
            break
        else:
            continue
    ans = ans%INF

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
MOD = 1000000007
num = int(input())
says = list(map(int, input().split()))

ans = 0
colors = 0
sets = [0, 0, 0]
for i in range(num):
    if max(sets) < says[i]:
        ans = 0
        break
    if colors == 0:
        sets[0] += 1
        colors += 1
        ans = 3
    elif colors == 1:
        if says[i] == 0:
            sets[1] += 1
            colors += 1
            ans *= 2
        else:
            sets[0] += 1
    elif colors == 2:
        if says[i] == 0:
            sets[2] += 1
            colors += 1
        else:
            if sets[0] == says[i]:
                sets[0] += 1
                if sets[1] == says[i]:
                    ans *= 2
            elif sets[1] == says[i]:
                sets[1] += 1
            else:
                ans = 0
                break
    elif colors == 3:
        if sets[0] == says[i]:
            sets[0] += 1
            if sets[1] == says[i] and sets[2] == says[i]:
                ans *= 3
            elif sets[1] == says[i] or sets[2] == says[i]:
                ans *= 2
        elif sets[1] == says[i]:
            sets[1] += 1
            if sets[2] == says[i]:
                ans *= 2
        elif sets[2] == says[i]:
            sets[2] += 1
        else:
            ans = 0
            break
#print(sets)
print(ans % MOD)

Submission status: Accepted

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

l = [3] + [0]*100000
ans = 1
for i in range(n):
    ans *= l[a[i]]
    l[a[i]+1] += 1 
    l[a[i]] -= 1
print(ans%1000000007)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import collections
N = int(input())
A_list = list(map(int, input().split()))

ans = 1
color_list = [0, 0, 0]
for i in range(N):
    pattern_num = 0
    for j in range(len(color_list)):
        if color_list[j] == A_list[i]:
            pattern_num += 1
    for j in range(len(color_list)):
        if color_list[j] == A_list[i]:
            color_list[j] += 1
            break
    ans *= pattern_num

print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
rbg = [0, 0, 0]
ans = 1
A = [int(a) for a in input().strip().split()]
for a in A:
    if rbg.count(a) == 0:
        print(0)
        exit()
    ans = (ans * rbg.count(a)) % (10 ** 9 + 7)
    rbg[rbg.index(a)] += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
modulo = 1000000007
comb = 1
stack = [0,0,0]
for time in s:
  idx = -1
  rep = 0
  for i in range(3):
    if time == stack[i]:
      idx = i
      rep += 1
  stack[idx] += 1
  comb *= rep
  comb %= modulo
print(comb)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

count = [0 for i in range(100000 + 89)]

if __name__ == "__main__":
	N = int(input())
	L = list(map(int, input().split()))
	ans = 1
	available_color = 3
	for x in L:
		if x == 0:
			ans *= available_color
			available_color -= 1
			count[0] += 1
		else:
			ans *= count[x - 1]
			count[x - 1] -= 1
			count[x] += 1
	print(ans % MOD)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
mod = 1000000007

RGB = [0,0,0]
ans = 1
for i in range(N):
    X = RGB.count(A[i])
    ans = (ans * X) % mod
    for j in range(3):
        if RGB[j] == A[i]:
            RGB[j] += 1
            break
print(ans)

Submission status: Accepted

Solution code:
INF = 1000000007

N = int(input())
Alist = list(map(int, input().split()))

ans = 3
rgb = [1, 0, 0]

for i in range(1, N):
    a = Alist[i]
    temp = 0
    check = False
    for j in range(3):
        if rgb[j] == a:
            temp += 1
            if not check:
                rgb[j] += 1
                check = True
    ans = ans * temp
    ans = ans % INF


if Alist[0] != 0:
    print(0)
else:
    print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
cnt = [0, 0, 0]
ans = 1
for e in a:
    idx = -1
    c = 0
    for i, cnt_e in enumerate(cnt):
        if e == cnt_e:
            c += 1
            idx = i

    if idx == -1:
        print(0)
        exit()

    cnt[idx] += 1
    ans *= c
    ans %= mod

print(ans)

Submission status: Accepted

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

count = 1

unused = [0] * N
max = 0

for a in A_list:
	if a > 0:
		if unused[a - 1] == 0:
			count = 0
			break
		count = (count * unused[a - 1]) % 1000000007
		unused[a - 1] -= 1
	unused[a] += 1
	if a == 0:
		max += 1
		if max > 3:
			count = 0
			break

if max == 0:
	print(0)
elif max == 1:
	print((count * 3) % 1000000007)
else:
	print((count * 6) % 1000000007)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
'''
def GI(V,E,DAG=False,index=0):
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[1:])
            bb=(inp[1:])
        g[a].append(b)
        if g[b].append(a)
        h.append(b)
'''

def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
 
show_flg=False
#show_flg=True

ans=1

n=I()
a=LI()

col=[-1]*3
for i in a:
    
    N=sum([1*(c+1==i) for c in col])
    show(col,N,i)
    ans*=N
    ans%=mo
    for j in range(3):
        c=col[j]
        if c+1==i:
            col[j]+=1
            break

print(ans%mo)   
show(c)

Submission status: Accepted

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

ans=1
zero=3
memo=[0]*n

for i in range(n):
  if a[i]==0:
    ans*=zero
    zero-=1
    memo[0]+=1
  else:
    ans*=(memo[a[i]-1]-memo[a[i]])
    ans%=mod
    memo[a[i]]+=1
print(ans)

Submission status: Accepted

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

ans = 1
clr = [0, 0, 0]
for i in range(N):
    ans *= clr.count(As[i])
    ans %= E
    for c in range(3):
        if As[i] == clr[c]:
            clr[c] += 1
            break
print(ans % E)

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readlines()
from functools import reduce
from operator import mul

n = int(inputs[0])
A = list(map(int, inputs[1].split()))
B = {0:0, 1:0, 2:0}
C = []
mod = 1000000007
for i in range(n):
    matches = [int(nb == A[i]) for nb in B.values()]
    if sum(matches) == 1:
        B[matches.index(1)] += 1
    elif sum(matches) == 2:
        B[matches.index(1)] += 1
        C.append(2)
    elif sum(matches) == 3:
        B[matches.index(1)] += 1
        C.append(3)
    else:
        print(0)
        break
else:
    print(reduce(mul, C) % mod)

Submission status: Accepted

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

X = [-1, -1, -1]
ans = 1
for a in A:
    t = X.count(a-1)
    ans = ans * t % 1000000007
    if a-1 not in X:
        print(0)
        exit()
    idx = X.index(a-1)
    X[idx] += 1
print(ans)

Submission status: Accepted

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

for x in a:
    up = max(up, x)

t = [0 for _ in range(up + 1)]

rgb = 3
ans = 1
for i in range(n):
    if a[i] == 0:
        t[a[i]] += 1
        ans *= rgb
        ans %= 1000000007
        rgb -= 1
    else:
        ans *= t[a[i] - 1]
        ans %= 1000000007
        t[a[i]] += 1
        t[a[i] - 1] -= 1


ans %= 1000000007
print(ans)
exit(0)

Submission status: Accepted

Solution code:
import sys

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

mod = (10**9) + 7
abc = [0] * 3
ans = 1
for i in range(N):
	pos = abc.count(A[i])
	if pos == 0:
		print(0)
		sys.exit()
	ind = abc.index(A[i])
	ans *= pos
	ans %= mod
	abc[ind] += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
p = 10**9 + 7
r = 1
cur = [0, 0, 0]
for i in range(N):
  fi = -1
  t = 0
  for c in range(3):
    if cur[c] == A[i]:
      t += 1
      fi = c
  if fi >= 0:
    cur[fi] += 1
  r = r * t % p

print(r)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
count = 1
data = [0 for i in range(len(A))]

for i in A:
  if i == 0:
    count *= 3-data[i]
  else:
    count *= data[i-1]-data[i]
  data[i]+=1
  count%=1000000007
print(count%1000000007)

Submission status: Accepted

Solution code:


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

aa = [0]*(n+1)
aa[0] = 3
ans = 1
for i in range(n):
    ans = ans * aa[a[i]] % k
    aa[a[i]] -= 1
    aa[a[i]+1] += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
x = [0,0,0]
c = 1
for i in range(n):
  cc = 0
  k = 0
  for j in range(3):
    if a[i] == x[j]:
      cc += 1
      k = j
  c = (c*cc)%1000000007
  x[k] += 1
print(c)

Submission status: Accepted

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

mod = 1000000007
fmax =0
smax =0
tmax =0

result = 1
for i in a:
    if i == fmax and i == smax and i == tmax:
        result = result * 3 % mod
        fmax += 1
    elif i == fmax and i == smax and i != tmax:
        result = result * 2 % mod
        fmax += 1
    elif i == fmax and i != smax and i == tmax:
        result = result * 2 % mod
        fmax += 1
    elif i != fmax and i == smax and i == tmax:
        result = result * 2 % mod
        smax += 1
    elif i == fmax and i != smax and i != tmax:
        fmax += 1
    elif i != fmax and i == smax and i != tmax:
        smax += 1
    elif i != fmax and i != smax and i == tmax:
        tmax += 1
    else:
        print(0)
        exit()
print(result)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
lis = [0 for i in range(n+1)]
lis[0] = 3
fl = True
ans = 1
for i in range(n):
  if i < a[i]:
    print(0)
    fl = False
    break
  else:
    k =  lis[a[i]] - lis[a[i]+1]
    ans *= k
    lis[a[i]+1] += 1
if fl:
  print(ans%1000000007)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''

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

    count = 1
    colors = {"r": 0, "g": 0, "b": 0}

    for a in A:
        _count = 0
        flag = 0
        for k in colors.keys():
            if int(a) == colors[k]:
                _count += 1
                if flag == 0:
                    flag = 1
                    colors[k] += 1
        count *= _count
        # print(int(a), _count)
    print(count % 1000000007)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
if A[0] != 0:
    print(0)
    exit()

cs = [0]*3
ans = 1
for a in A:
    c = cs.count(a)
    if c==0:
        print(0)
        exit()
    ans *= c
    ans %= MOD
    i = cs.index(a)
    cs[i] += 1

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=list(map(int,input().split()))
D={}
mod=((10**9)+7)
ans=1
for i in range(N):
    try:
        if S[i]==0:
            if 0 not in D:
                D[0]=1
                ans*=3
            elif D[0]==1:
                D[0]+=1
                ans*=2
            elif D[0]==2:
                D[0]=3
            else:
                ans=0
        elif S[i] not in D:
            ans*=D[S[i]-1]
            ans%mod
            D[S[i]]=1
        else:
            if D[S[i]]==1:
                ans*=(D[S[i]-1]-1)
                D[S[i]]+=1
                ans%=mod
            elif D[S[i]]==2:
                ans*=(D[S[i]-1]-2)
                D[S[i]]+=1
                ans%=mod
            else:
                ans=0
    except:
        ans=0
    #print(ans)
print(ans%mod)

Submission status: Accepted

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

mod=1000000007
ans=1
r,b,g=0,0,0
r2,b2,g2=-1,-1,-1
for i in a:
    if r2==r and b2==b and g2==g:
        print(0)
        exit()
    r2=r
    b2=b
    g2=g
    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: Accepted

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

c = [0 for k in range(max(A)+2)]
ans = 1
MOD = 1000000007

c[0] = 3
for k in range(N):
    ans *= c[A[k]] - c[A[k]+1]
    c[A[k]+1] += 1
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:


n = int(input())
la = list(map(int,input().split()))
l = [0,0,0]
lb = []
c=1
for i in range(0,n):
    lb.append(l.count(la[i]))
    for j in range(0,3):
        
        if la[i] == l[j]:
            l[j] = l[j] + 1
            break
        else:
            continue

for i in range(0,n):
    c = c * lb[i]
print(c%1000000007)

Submission status: Accepted

Solution code:
MOD = 1000000007
N = int(input())
A = list(map(int, input().split()))
x = [1, 0, 0]
ans = 3

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

if A[0] != 0:
    ans = 0
print(ans % MOD)

Submission status: Accepted

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

pattern = 1
hats = [0, 0, 0]
for a in A:
    if pattern == 0:
        break
    i = 0
    for j in range(3):
        if a == hats[j]:
            i += 1
    pattern *= i
    for j in range(3):
        if a == hats[j]:
            hats[j] += 1
            break
    if pattern >= 1000000007:
        pattern = pattern % 1000000007

print(pattern)

Submission status: Accepted

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

n = int(input())
a_ = list(map(int, input().split()))
MOD = 1000000007

cnt = 1
rbg = [0, 0, 0]

for a in a_:
    tmp = 0
    flg = 0
    for i in range(3):
        if rbg[i] == a:
            tmp += 1
            if flg == 0:
                rbg[i] += 1
            flg = 1
    cnt = cnt*tmp%MOD
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=1000000007
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    c=[0,0,0]
    ans=1
    for i in range(N):
        tmp=0
        color=-1
        for x in range(3):
            if A[i]==c[x]:
                tmp+=1
                color=x
        ans*=tmp
        ans%=MOD
        c[color]+=1
    print(ans%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

pattern = 1
hats = [0, 0, 0]
for a in A:
    if pattern >= 1000000007:
        pattern = pattern % 1000000007
    if pattern == 0:
        break
    i = 0
    for j in range(3):
        if a == hats[j]:
            i += 1
    pattern *= i
    for j in range(3):
        if a == hats[j]:
            hats[j] += 1
            break

print(pattern % 1000000007)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
dp = [0] * 1000000
mod = 10**9 + 7
ans = 1
dp[0] = 3
for a in As:
    a += 1
    ans *= dp[a-1]-dp[a]
    ans %= mod
    dp[a] += 1
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
n = int(input())
L = [int(i) for i in input().split()]
now = [0, 0, 0] # [R, G, B]

s = 1
now[0] = 1
if L[0] != 0:
  print(0)
  sys.exit()

  
for i in range(n-1):
  c = L[i+1]
  s = s*now.count(c)
  for j in range(3):
    if now[j] == c:
      now[j] += 1
      break

print((s*3)%1000000007)

Submission status: Accepted

Solution code:
N = int(input())
src = list(map(int,input().split()))
cnt = [0]*(N+1)
ans = 1
mod = 10**9+7
for i in src:
    if i == 0:
        ans *= 3-cnt[0]
        cnt[0] += 1
    else:
        if cnt[i] == 0:
            ans *= cnt[i-1]
            cnt[i] += 1
        else:
            ans *= cnt[i-1] -cnt[i]
            cnt[i] += 1
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
AtCoder A
"""

import sys, math, random
import numpy as np

# N = int(input())
# A = list(map(int,input().split())) # N row 1 column
# A = [int(input()) for _ in range(N)] # 1 row N column
# S = str(input()) # str(input()) == input() -> 'abc'
# S = list(input()) # abc -> ['a','b','c']
# S.replace('ABC','X') # "testABCABC" -> "testXX"

inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    N=I()
    A=LI()
    out=1
    tmp=[-1,-1,-1]
    for a in A:
        out*=tmp.count(a-1)
        if tmp[0]==a-1:
            tmp[0]+=1
        elif tmp[1]==a-1:
            tmp[1]+=1
        else:
            tmp[2]+=1
    print(out%mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

a,b,c = [-1],[-1],[-1]
ans = 1
#「どのグル－プに行けるか」 を行けるグループ数だけかけていく
for i in range(N):
  tmp = 0
  if(a[-1] == A[i]-1): 
      tmp += 1
      if(tmp == 1): a.append(A[i])
  if(b[-1] == A[i]-1): 
      tmp += 1
      if(tmp == 1): b.append(A[i])
  if(c[-1] == A[i]-1): 
      tmp += 1
      if(tmp == 1): c.append(A[i])
  ans = ans*tmp
  ans = ans%((10**9)+7)
  
print(ans)

Submission status: Accepted

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

for i in range(N):
  ans *= C[A[i]]-C[A[i]+1]
  ans %= MOD
  C[A[i]+1] += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

b = [0] * (n+1)
b[0] = 3

ans = 1
for ai in a:
    ans *= b[ai]
    ans %= 1000000007
    b[ai] -= 1
    b[ai+1] += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
count = [0] * n
ans = 1
mod = 10 ** 9 + 7
for i in a:
    if i == 0:
        ans = ans * (3 - count[0]) % mod
    else:
        ans = ans * max(0, (count[i - 1] - count[i])) % mod
    count[i] += 1
print(ans % mod)

Submission status: Accepted

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

col = [0,0,0]

ans = 1

for i in range(n):
    if not a[i] in col:
        print(0)
        exit()
    else:
        ans *= col.count(a[i])
        ans %= mod
        col[col.index(a[i])] += 1

if sum(col) != n:
    print(0)
    exit()

print(ans%mod)

Submission status: Accepted

Solution code:
n=int(input())
lists=list(map(int,input().split()))
counter=1
uselist=[0,0,0]
for j in range(n):
    human=lists[j]
    sub=0
    for p in range(3):
        if uselist[p]==human:
            sub+=1
    for q in range(3):
        if uselist[q]==human:
            uselist[q]+=1
            break
    counter=counter*sub
    counter=counter%(10**9+7)
if lists[0]==0:
    print(counter)
else:
    print(0)

Submission status: Accepted

Solution code:
# def i():
#     yield "100000"
#     a = 0
#     b = 0
#     c = 0
#     l = []
#     for i in range(100000):
#         import random
#         r = random.randint(0, 2)
#         if r == 0:
#             l.append(str(a))
#             a += 1
#         elif r == 1:
#             l.append(str(b))
#             b += 1
#         else:
#             l.append(str(c))
#             c += 1
#     yield " ".join(l)
# input = i().__next__
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    cur = 1
    nums = []
    for i in range(N):
        if A[i] == 0:
            cur *= 1
            nums.append(0)
            continue
        #A[i] != 0
        cnt = 0
        for j, n in enumerate(nums):
            if n == A[i] - 1:
                if cnt == 0:
                    if len(nums) <= j:
                        print(0)
                        return
                    nums[j] += 1
                cnt += 1
        cur *= cnt
        cur %= 10**9+7
        # print(nums)
    m = [0, 3, 6, 6]
    if len(nums) >= 4:
        print(0)
        return
    
    print((cur * m[len(nums)]) % (10**9+7))
main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
kosu=[0 for i in range(n)]
kosu0=3
josu=0
ans=1
cnt=0
for i in a:
  if i==0:
    josu=kosu0
    kosu0-=1
    kosu[i]+=1
  else:
    josu=kosu[i-1]-kosu[i]
    kosu[i]+=1
  ans*=josu
  ans%=1000000007
  josu=0
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
d = [int(x) for x in stdin.readline().rstrip().split()]
a = [0] * n
k = 1
for i in range(n):
    if d[i] == 0:
        k *= (3 - a[0])
        a[0] += 1
    else:
        k *= ((a[d[i]-1])-a[d[i]])
        a[d[i]] += 1
print(k % 1000000007)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    *na, = map(int, read().split())
    n, a = na[0], na[1:]
    xyz = [0, 0, 0]
    p = 1
    for i in range(n):
        p *= sum([j==k for j, k in zip([a[i]]*3, xyz)])
        if xyz[0]==a[i]: xyz[0]+=1; continue
        if xyz[1]==a[i]: xyz[1]+=1; continue
        if xyz[2]==a[i]: xyz[2]+=1; continue

    print(p%(10**9+7))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

mul = 3 if L[-1] == n-1 else 6
MOD = 1000000007

ans = 1
zero_counter = 0
available = []
for elm in L:
    if elm == 0:
        zero_counter += 1
        if zero_counter > 3:
            ans = 0
            break
        available.append(elm)
    else:
        counter = available.count(elm-1)
        if counter == 0:
            ans = 0
            break
        ans *= counter
        available.remove(elm-1)
        available.append(elm)
        ans = ans % MOD

ans = (ans * mul) % MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
hats = list(map(int, input().split()))
MOD = 1000000007
r = 0
g = 0
b = 0
ans = 1

for h in hats:
    if ans == 0:
        break
    poss = 0
    can_add = True
    if r == h:
        poss += 1
        if can_add:
            r += 1
            can_add = False
    if g == h:
        poss += 1
        if can_add:
            g += 1
            can_add = False
    if b == h:
        poss += 1
        if can_add:
            b += 1
            can_add = False        
    ans *= poss
    ans = ans % MOD
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Alist = list(map(int, input().split()))
nums = [0, 0, 0]
ans = 1
for i in range(N):
    try:
        A = Alist[i]
        ans = (ans * nums.count(A)) % (10**9 + 7)
        nums[nums.index(A)] += 1
    except:
        print(0)
        break
else:
    print(ans)

Submission status: Accepted

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

ans = 1
mod = 10 ** 9 + 7
l = [0] * (max(A)+1)

for a in A:
    if not a:
        ans *= (3 - l[a])
    else:
        ans *= (l[a-1] - l[a])
    l[a] += 1

    if ans > mod:
        ans = ans % mod

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9 + 7
ans = 1
memo = {}
for i in range(n+2):
    memo[i] = 0
memo[0] = 3

for i in range(n):
    ans *= memo[a[i]]
    memo[a[i]] -= 1
    memo[a[i]+1] += 1
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import itertools
mod = 10**9+7

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

rgb = [0,0,0]
# r = 1
# b = 0
# g = 0
ans = 1

for i in range(0, n):
    cnt = a[i]
    conb = 0
    isFirst = True
    for j in range(3):
        eachCnt = rgb[j]
        if cnt == eachCnt:
            conb += 1
            if isFirst:
                rgb[j] += 1
                isFirst = False
    # print('conb', conb)
    ans *= conb % mod

# print('ans', ans)
print(ans % mod)

Submission status: Accepted

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

m = max(A)

L = [3] + [0] * (m + 1)
K = [0] * len(A)
count = 3
for i in range(len(A)):
    K[i] = L[A[i]]
    L[A[i]] -= 1
    L[A[i] + 1] += 1

count = 1
for k in K:
    count *= k

print(count % 1000000007)