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

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

Solution (Python):

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)

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

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

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

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

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

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

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

Solution (Python):

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(ans % MOD)

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

Solution (Python):

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

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

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

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

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

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

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

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

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


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)

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

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

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

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

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

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

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

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

Solution (Python):


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)

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

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

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

Solution (Python):


''' 
------------------------
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(count % 1000000007)



if __name__ == '__main__':
    main()

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

Solution (Python):
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%mod)

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

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

Solution (Python):


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)

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

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

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

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

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

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

Solution (Python):
import sys
n = int(input())
L = [int(i) for i in input().split()]
now = [0, 0, 0] 

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)

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

Solution (Python):

"""
AtCoder A
"""

import sys, math, random
import numpy as np








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

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

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

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

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

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

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

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

Solution (Python):




















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
        
        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
        
    m = [0, 3, 6, 6]
    if len(nums) >= 4:
        print(0)
        return
    
    print((cur * m[len(nums)]) % (10**9+7))
main()

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

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

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

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

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

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

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

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

Solution (Python):
import itertools
mod = 10**9+7

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

rgb = [0,0,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
    
    ans *= conb % mod


print(ans % mod)

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

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    C = [0, 0, 0]
    ans = 1
    for x in a:
        d = C.count(x)
        if d == 0:
            ans = 0
            break
        ans *= d
        ans %= 1000000007
        ind = C.index(x)
        C[ind] += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N = II()
    A = LMIIS()
    numUsed = [0] * N
    ans = 1
    mod = 10**9 + 7
    for i in range(len(A)):
        if A[i] == 0:
            ans *= 3 - numUsed[0]
            
            numUsed[0] += 1
        else:
            ans *= (numUsed[A[i]-1] - numUsed[A[i]])
            
            numUsed[A[i]] += 1
        ans %= mod
    print(ans)

    





if __name__ == '__main__':
    main()

Solution (Python):
import sys
def cmb(n,r,mod):
  if r<0 or r>n:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n*2):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

ct=[0,0,0]
ans=1
for i in range(n):
  f=0
  ct2=0
  for j in range(3):
    if a[i]==ct[j]:
      if ct2==0:
        ct[j]+=1
      ct2+=1
  ans*=ct2
print(ans%mod)

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

mod = 10**9 + 7


ans = 1
cnt = [0 for i in range(3)]
for i in range(n):
    count = 0
    for j in range(3):
        if cnt[j] == a[i]:
            count += 1
    ans *= count
    ans %= mod
    for j in range(3):
        if cnt[j] == a[i]:
            cnt[j] += 1
            break


print(ans)

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

rgb = [0, 0, 0]
ans = 1
for a in A:
    if a not in rgb:
        print(0)
        break
    ans = (ans * rgb.count(a)) % 1000000007
    idx = rgb.index(a)
    rgb[idx] += 1
else:
    print(ans)

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

ans = 1
color = 3
counter = [0 for i in range(n+1)]
for i,value in enumerate(a):
    if value == 0:
        tmp = 3 - counter[0]
    else:
        tmp = counter[value - 1] - counter[value]
    ans = ans * tmp % mod
    counter[value] += 1
print(ans)

Solution (Python):
import itertools
N = int(input())
A = [int(x) for x in input().split()]
max_A = max(A)
counter = [[] for _ in range(max_A + 1)]
for i, a in enumerate(A):
    counter[a].append(i)
if any(len(counter[i]) > 3 for i in range(max_A + 1)):
    print(0)
    quit()
if any(len(counter[i]) < len(counter[i+1]) for i in range(max_A)):
    print(0)
    quit()

ans = [3, 6, 6][len(counter[0])-1]
mod = 10 ** 9 + 7
for i in range(max_A):
    cnt = 0
    for li in itertools.permutations(counter[i], len(counter[i+1])):
        cnt += all(v1 < v2 for v1, v2 in zip(li, counter[i+1]))
    ans = (ans * cnt) % mod
print(ans)

Solution (Python):
mod = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))
r = 0
b = 0
y = 0
ans = 1
for i in range(N):
    f = 0
    if r == A[i]:
        r += 1
        f += 1
    if b == A[i]:
        if f == 0:
            b += 1
        f += 1
    if y == A[i]:
        if f == 0:
            y += 1
        f += 1
    ans = (ans*f) % mod
print(ans)