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):
def main():
    import sys
    N=int(input())
    MOD=1000000007
    
    a=list(map(int,input().split()))
    c=[0,0,0]
    ans=1
    for i in range(N):

        if a[i]!=c[0] and a[i]!=c[1] and a[i]!=c[2]:
            print(0)
            sys.exit()

        if c[1]==c[0] and c[2]==c[0]:
            ans=(ans*3)%MOD
            c[0]+=1

        elif c[0]==c[1]:
            if c[0]==a[i]:
                c[0]+=1
                ans=(ans*2)%MOD
            else:
                c[2]+=1

        elif c[0]>c[1] and c[1]==c[2]:
            if c[0]==a[i]:
                c[0]+=1
            else:
                ans=(ans*2)%MOD
                c[1]+=1
            
        else:
            if c[0]==a[i]: c[0]+=1
            if c[1]==a[i]: c[1]+=1
            if c[2]==a[i]: c[2]+=1
        
        c.sort(reverse=True)
    print(ans)


 
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
ans = 1
colors = [0] * 3
mod = 10**9 + 7

for a in A:
    ans = (ans * colors.count(a)) % mod
    if ans != 0:
        i = colors.index(a)
        colors[i] += 1

print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def solve():
    n = II()
    d = defaultdict(int)
    a = LI()
    ans = 1
    d[0] = 3
    for i in range(n):
        y = d[a[i]]
        ans *= y
        ans %= mod
        d[a[i]] -= 1
        d[a[i] + 1] += 1
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
ans = 1
numofcolor = [0] * (N+1)
numofcolor[0] = 3
for i in range(N):
    ans *= numofcolor[A[i]]
    ans %= 1000000007
    numofcolor[A[i]] -= 1
    numofcolor[A[i]+1] += 1
print(ans)

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

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

if n == 1:
    if A[0] == 0:
        print(3)
    else:
        print(0)
    exit()


if A[0] != 0:
    print(0)
    exit()
for a in A[1:]:
    count = hats.count(a)
    if count == 0:
        print(0)
        exit()

    idx = hats.index(a)
    hats[idx] += 1
    ans *= count
    ans %= mod

print(ans)

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

MOD = 10 ** 9 + 7

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

ans = 1

for x in a:
    ans = ans * c.count(x-1) % MOD
    for i in range(3):
        if c[i] == x-1:
            c[i] = x
            break

print(ans)

Solution (Python):
inpl = lambda: list(map(int,input().split()))
MOD = 10**9+7
N = int(input())
A = inpl()
ans = 1
nc = [0] * 3
for i in range(N):
    k = 0
    a = A[i]
    while nc[k] > a:
        k += 1
        if k > 2:
            print(0)
            exit()
    if nc[k] < a:
        print(0)
        exit()
    if k <= 1 and nc[k+1] == a:
        s = 2
        if k == 0 and nc[k+2] == a:
            s = 3
        ans = ans * s % MOD
    nc[k] += 1
print(ans)

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

MOD=10**9+7
rgb=[-1]*3

count=1
buf=0
for i in range(n):
    c=0
    for j in range(3):
        if rgb[j]+1==a[i]:
            c+=1
            buf=j
    
    count*=c
    count%=MOD
    rgb[buf]+=1
print(count)

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

ans = 1
res = 10 ** 9 + 7
B = 0
R = 0
G = 0
for a in A:
    cnt = 0
    if a == B:
        cnt += 1
    else:
        pass
    if a == R:
        cnt += 1
    else:
        pass
    if a == G:
        cnt += 1
        G += 1
    elif a == R:
        R += 1
    else:
        B += 1
    ans = ans * cnt % res
print(ans)

Solution (Python):
mod=1000000007
n=int(input())
a=list(map(int,input().split()))
c=1
r=0
g=0
b=0
for x in a:
    tmp=0
    if x==b:
        tmp+=1
    if x==g:
        tmp+=1
    if x==r:
        tmp+=1
    if x==b:
        b+=1
    elif x==g:
        g+=1
    else :
        r+=1
    c*=tmp
    c%=mod
print(c)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n = II()
    a_s = LI()
    d = [0, 0, 0]
    ans = 1
    for i in a_s:
        flag = True
        tmp = 0
        for index, j in enumerate(d):
            
            if j == i:
                tmp += 1
                if flag:
                    d[index] += 1
                    flag = False
        ans = ans * tmp % MOD
        
    print(ans)





if __name__ == '__main__':
    main()

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

DIV = 1000000007

ls = [0]*100000

ans = 1
for i in a:
    ls[i] += 1
    if i == 0:
        ans *= 4 - ls[i]
    else:
        ans *= ls[i-1]-ls[i]+1

    ans %= DIV

print(ans)

Solution (Python):
n,*d=map(int,open(0).read().split())
a,b,c=0,0,0
ans=1
for i in d:
    ans=ans*[a,b,c].count(i)%1000000007
    if i==a:
        a+=1
    elif i==b:
        b+=1
    elif i==c:
        c+=1
print(ans)

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

stack = [0,0,0]

ans = 1
for a in al:
    p = stack.count(a)
    ans *= p
    ans %= 1000000007
    for i in range(3):
        if stack[i] == a:
            stack[i] += 1
            break

print(ans)

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

Solution (Python):
from collections import Counter

MOD = 10**9 + 7

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

ptns = Counter([(0, 0, 0)])

for A in As:
    ptn2s = Counter()
    for ptn, num in ptns.items():
        for i in range(3):
            if ptn[i] == A:
                ptn2 = list(ptn)
                ptn2[i] += 1
                ptn2s[tuple(ptn2)] += num
                ptn2s[tuple(ptn2)] %= MOD
    ptns = ptn2s


print(sum(ptns.values()) % MOD)

Solution (Python):
import sys
input = sys.stdin.readline
MOD=10**9+7
n=int(input())
l=list(map(int,input().split()))
lc=[0]*(n+1)
ans=1
tmp=3
for i in l:
    if i==0:
        ans*=tmp
        ans%=MOD
        tmp-=1
    else:
        ans*=lc[i-1]
        ans%=MOD
        lc[i-1]-=1
    lc[i]+=1
print(ans)

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

cnt = [0] * (max(A) + 2)
cnt[-1] = 1
ans = 1
for a in A:
    if a == 0:
        cnt[0] += 1
        continue
    ans = (ans * (cnt[a - 1] - cnt[a])) % mod
    cnt[a] += 1

if max(cnt) == 1:
    print((ans*3) % mod)
elif max(cnt) == 3:
    print((ans * 6) % mod)
elif max(cnt) == 2:
    print((ans * 6) % mod)
else:
    print(0)

Solution (Python):
n = int(input())
L = [-1,-1,-1]
ans = 1
color = list(map(int,input().split()))
for i in range(n):
    k = L.count(color[i]-1)
    ans = (ans*k)%(10**9+7)
    for j in range(3):
        if L[j] == color[i]-1:
            L[j] += 1
            break
print(ans)

Solution (Python):
n=int(input())
al=list(map(int,input().split()))
num=[0 for i in range(n+2)]
num[-1]=3
ans=1

for i in range(n):
    ans*=num[al[i]-1]
    ans=ans%1000000007
    num[al[i]-1]-=1
    num[al[i]]+=1

print(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):
import numpy as np


if __name__ == "__main__":
    n = int(input())
    a = np.array(list(map(int, input().split())))
    mod = 10**9+7

    memo = np.zeros(n+10, dtype=int)
    memo[0] = 3
    ans = 1
    for i in a:
        mae = memo[i]
        now = memo[i+1]
        ans *= mae-now
        ans %= mod

        memo[i+1] += 1

    print(ans)

Solution (Python):
mod = 10**9 + 7
N = int(input())
A = [int(i) for i in input().split()]
M = [0]*10**5

ans = 1
for i, a in enumerate(A):
    if a == 0:
        ans *= 3-M[0]
        M[0] += 1
    else:
        ans *= M[a-1]-M[a]
        M[a] += 1
    ans %= mod

print(ans)

Solution (Python):
M = 1000000007
N = int(input())
A = list(map(int, input().split()))
count = [0 for i in range(N+1)]
count[N] = 3
ans = 1
for ai in A:
    ans = (ans * count[ai-1]) % M
    count[ai] += 1
    count[ai-1] -= 1
print(ans)

Solution (Python):


import sys
import math
import collections


n=int(input())

tmp = input().split()
s = list(map(lambda a: int(a), tmp))

a=-1
b=-1
c=-1

ans=1

for i in range(0,n):
	tmp=0

	if(s[i]-1==a):
		tmp+=1
	if(s[i]-1==b):
		tmp+=1
	if(s[i]-1==c):
		tmp+=1
	ans*=tmp
	if(s[i]-1==a):
		a+=1
	elif(s[i]-1==b):
		b+=1
	elif(s[i]-1==c):
		c+=1
print(ans%1000000007)

Solution (Python):
n = int(input())
a_array = map(int, input().split())
color = [0, 0, 0]
ans = 1
for a in a_array:
    count = 0
    for i in range(3):
        if color[i] == a:
            if not count:
                color[i] += 1
            count += 1
    ans *= count
    ans %= 1000000007
print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 1
l = [0] * 3
for x in a:
    ans *= l.count(x)
    ans %= MOD
    for j in range(3):
        if l[j] == x:
            l[j] += 1
            break
print(ans)

Solution (Python):
from collections import defaultdict
MOD = 1000000007
N = int(input())
A = list(map(int, input().split()))

ans = 1
d = defaultdict(int)
for a in A:
    if a == 0:
        ans *= 3 - d[a]
        d[a] += 1
        continue
    ans *= d[a - 1] - d[a]
    ans %= MOD
    d[a] += 1
print(ans)

Solution (Python):


import math
import sys
import itertools


n =int(input())


a = [int(i) for i in input().split()]
p=q=r=0
modnum = 1000000007
answer=1
for i in range(n):
    s=0
    if p == a[i]:
        s += 1
        p += 1
    if q == a[i]:
        s += 1
        if s==1:
            q += 1
    if r == a[i]:
        s += 1
        if s == 1:
            r += 1

    answer = (answer * s) % modnum

print(answer)

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

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
R = 0
G = 0
B = 0
output = 1
for i in range(N):
    Rf = 0
    Gf = 0
    Bf = 0
    if A[i]==R:
        Rf = 1
    if A[i]==G:
        Gf = 1
    if A[i]==B:
        Bf = 1
    S = Rf+Gf+Bf
    if Rf==1:
        R+=1
    elif Gf ==1:
        G+=1
    elif Bf==1:
        B+=1
    output *= S
    output = output%1000000007
print(output)

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

Solution (Python):
mod = 1000000007

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(M, a):
    count = M.count(a)
    if count == 0:
        return 0

    for i in range(2, -1, -1):
        if M[i] == a:
            M[i] += 1
            break

    return count


def main():
    N = int(input())
    A = read_list()

    M = [0, 0, 0]
    res = 1

    for a in A:
        res *= f(M, a)
        res %= mod
        if res == 0:
            print(0)
            return

    print(res % mod)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9+7

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
RGB = [0]*3
ans = 1
for i in A:
    count = 0
    for j in RGB:
        if i == j:
            count += 1
    if count == 0:
        print(0)
        exit()
    RGB[RGB.index(i)] += 1
    ans = (ans * count)% MOD

print(ans)

Solution (Python):
n = int(input())
xs = list(map(int, input().split()))
A = max(xs)
dp = [0] * (A+1)
MOD = 1000000007

r = 1
zc = 0
for x in xs:
    if x == 0:
        zc += 1
    else:
        r = r * dp[x-1] % MOD
        dp[x-1] -= 1
    dp[x] += 1
if zc == 0 or zc >= 4:
    rr = 0
elif zc == 1:
    rr = 3
else:
    rr = 6
print(r * rr % MOD)

Solution (Python):
import sys
input = sys.stdin.readline

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

mod = 10**9+7
ans = 1
P = [0, 0, 0]
for a in A:
    c = P.count(a)
    ans = ans*c%mod
    for i in range(3):
        if P[i] == a:
            P[i] += 1
            break
    
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()



def main():
    color = [-1] * 3
    n = ii()
    A = lmi()
    num = [0] * (max(A) + 10)
    ans = 1
    num[0] = 3
    for i in range(n):
        num[A[i] + 1] += 1
        ans *= num[A[i]]
        num[A[i]] -= 1
        ans %= 1000000007
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
res = 1
amari = 1000000007
rgb = [0, 0, 0]

for a in A:
    cnt = 0
    j = 0
    for i in range(3):
        if rgb[i] == a:
            cnt += 1
            j = i
    rgb[j] += 1
    res *= cnt
    res %= amari

print(res)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
ans=1
b=[0,0,0]
for i in range(n):
  c=0
  for j in range(3):
    if a[i]==b[j]:
      c=c+1
  if a[i]==b[0]:
    b[0]=a[i]+1
  elif a[i]==b[1]:
    b[1]=a[i]+1
  elif a[i]==b[2]:
    b[2]=a[i]+1
  ans=ans*c%(10**9+7)
print(ans)

Solution (Python):
MOD = 1000000007

def main():
	n = int(input())
	a = list(map(int,input().split()))
	h = [-1,-1,-1]
	ans = 1
	for i in range(n):
		
		ans = ans*h.count(a[i]-1) % MOD
		for j in range(3):
			if h[j] == a[i]-1:
				h[j] = a[i]
				break
	hn = h.count(-1)
	if hn == 0:
		if h[0] == h[1] and h[1] == h[2]:
			pass
		elif h[0] != h[1] and h[1] != h[2] and h[2] != h[0]:
			pass
		else:
			pass
	elif hn == 1:
		pass
	elif hn == 2:
		pass
	print(ans)

main()

Solution (Python):
N = int(input())

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

MOD = 1000000007

R = 0
B = 0
G = 0

ans = 1
for a in A:
    
    count = 0
    if a == R:
        count += 1
    if a == B:
        count += 1
    if a == G:
        count += 1

    ans *= count

    if a == R:
        R += 1
    elif a == B:
        B += 1
    elif a == G:
        G += 1
    ans %= MOD

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7
resi = dict()
for i in range(100000+1):
    resi[i] = 0
resi[0] = 3

cnt = 1
for i in range(N):
    if A[i] == 0:
        cnt *= resi[0]
        cnt %= MOD
        resi[0] -= 1
        resi[1] += 1
    else:
        cnt *= resi[A[i]]
        cnt %= MOD
        resi[A[i]] -= 1
        resi[A[i]+1] += 1
    if resi[A[i]+1] > 3 or resi[A[i]] < 0:
        print(0)
        exit()

print(cnt)

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

num = [0 for _ in range(n)]
count_zero = 0
ans = 1
mod = 1000000007

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

Solution (Python):
import sys

X = [0,0,0]

n = int(input())
A = [int(x) for x in input().split()]

res = 1
for a in A:
    res = res*X.count(a) % 1000000007
    if X.count(a):
        X[X.index(a)] += 1
    else:
        print(0)
        sys.exit(0)
print(res)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]

C=[0,0,0]
ans=1
for x in A:
    ans *= C.count(x)
    ans%=mod
    for i,a in enumerate(C):
        if a==x:
            C[i]+=1
            break
print(ans)

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]

mod = 10**9+7
r = 0
g = 0
b = 0

cnt = 1

for i in range(N):
    if A[i] == r:
        if r == g and r == b:
            cnt *= 3
        elif r == g or r == b:
            cnt *= 2
        r += 1
    elif A[i] == g:
        if g == b:
            cnt *= 2
        g += 1
    elif A[i] == b:
        b += 1
    else:
        cnt = 0
        break
        
    cnt %= mod
    
print(cnt)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
d=[-1,-1,-1]
x=1
for i in a:
  b=0
  f=True
  for j in range(3):
    if d[j]==i-1:
      b+=1
      if f:
        f=False
        d[j]=i
  x*=b
  x%=10**9+7
print(x)

Solution (Python):
mod=10**9+7
n,*a=map(int,open(0).read().split())
d=[-1,-1,-1]
ans=1
for x in a:
	ans *= d.count(x-1)
	ans %= mod
	for i in range(3):
		if d[i] == x - 1:
			d[i] = x
			break
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
dp = [0 for i in range(n+1)]
if a[0] != 0:
    print(0)
    exit()
dp[0] = 3
r,g,b = 1,0,0
for i in range(1,n):
    if a[i] == r:
        if r == g and g == b:
            dp[i] = dp[i-1]*3
        elif r == g or r == b:
            dp[i] = dp[i-1]*2
        else:
            dp[i] = dp[i-1]
        dp[i] %= mod
        r += 1
    elif a[i] == g:
        if g == b:
            dp[i] = dp[i-1]*2
        else:
            dp[i] = dp[i-1]
        dp[i] %= mod
        g += 1
    elif a[i] == b:
        dp[i] = dp[i-1]
        b += 1
    else:
        dp[i] = 0
print(dp[n-1])

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()))
s=[3]+[0]*(n+1)
m=10**9+7
c=1
for i in a:
    s[i+1]+=1
    c=(c*s[i])%m
    s[i]-=1
    if s[i]<0:
        print(0)
        break
else:
    print(c)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    ans=1
    C=[0]*(n+1)
    C[0]=3
    for a in A:
        ans*=C[a]
        ans%=MOD
        C[a]-=1
        C[a+1]+=1
    print(ans)
resolve()

Solution (Python):
import sys
input=sys.stdin.readline
INF=10**9+7
n=int(input())
a_list=list(map(int,input().split()))
l=[0,0,0]
ans=1
for i in range(n):
    c=0
    for j in l:
        if j==a_list[i]:
            c+=1
    ans=(ans*c)%INF
    for j in range(3):
        if l[j]==a_list[i]:
            l[j]+=1
            break
print(ans)

Solution (Python):
MOD = 1000000007


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


ans = 1
counter = [0, 0, 0]
for i in range(n):
    index = list()
    for j in range(len(counter)):
        if counter[j] == A[i]:
            index.append(j)

    ans *= len(index)
    ans = ans % MOD
    if len(index) == 0:
        break
    else:
        counter[index[0]] += 1

print(ans)

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

mod = 1000000007

c = [0,0,0]
ans = 1
for a in A:
    ans *= c.count(a)%mod
    for i in range(3):
        if c[i]==a:
            c[i]+=1
            break

print(ans%mod)

Solution (Python):

n = int(input())
s = list(map(int, input().split()))
inf =  1000000007

a, b, c = 0, 0, 0
ans = 1

for i in range(n):
	tmp = [a, b, c].count(s[i])
	ans *= tmp
	ans %= 1000000007
	if s[i] == a:
		a += 1
	elif s[i] == b:
		b += 1
	else:
		c += 1
	

print(ans)

Solution (Python):
from collections import Counter
MOD = 10 ** 9 + 7
N = int(input())
As = list(map(int, input().split()))

counts = [-1, -1, -1]
ans = 1

for a in As:
    ct = Counter(counts)
    ans *= ct[a-1]
    ans %= MOD
    for i in range(3):
        if counts[i] == a-1:
            counts[i] += 1
            break
print(ans)

Solution (Python):
a=int(input())
b=list(map(int,input().split()))
c=[0,0,0]
ans=1
mod=1000000007
for i in b:
  d=0
  for j in c:
    if i==j:
      d+=1
  if d==0:
    print(0)
    exit()
  else:
    ans=ans*d%mod
    for j in range(3):
      if i==c[j]:
        c[j]+=1
        break
print(ans)

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())
MOD = 1000000007

next = [0,0,0]
ans = 1

for ai in a:
    cnt = next.count(ai)
    if cnt == 0:
        ans = 0
        break
    else:
        idx = next.index(ai)
        next[idx] += 1
        ans *= cnt
        ans %= MOD

print(ans)

Solution (Python):
def main():
    
    MAX = 1000000007
    n = int(input())
    a = list(map(int, input().split()))

    li = [0 for _ in range(100002)]
    li[-1] = 3

    ans = 1
    cap = [0, 0, 0]
    for i in a:
        ans *= li[i-1]-li[i]
        ans = ans%MAX
        li[i] += 1
    print(ans)


    


if __name__ == '__main__':
    main()

Solution (Python):
def p_e():
    n = int(input())
    *A, = map(int, input().split())
    mod = 1000000007
    dp = [0] * 3
    ans = 1
    for a in A:
        num = 0
        flg = True
        
        for j in range(3):
            if dp[j] == a:
                if flg:
                    dp[j] += 1
                    flg = False
                num += 1
        ans *= num
        ans %= mod

    print(ans)
    
p_e()

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

c = [0, 0, 0]

ans = 1
for i in range(n):
    count = 0
    for _c in c:
        if a[i] == _c:
            count += 1

    ans = ans * count % 1000000007
    if c[0] == a[i]:
        c[0] += 1
    elif c[1] == a[i]:
        c[1] += 1
    else:
        c[2] += 1

print(ans)

Solution (Python):
def examE(mod):
    N = I()
    A = LI()
    a =[0,0,0]
    cur = 1
    for i in A:
        if a[0]==i:
            if a[0]==a[1]:
                if a[1]==a[2]:
                    cur *= 3
                else:
                    cur *=2
            a[0]+=1
        elif a[1]==i:
            if a[1] == a[2]:
                cur *= 2
            a[1] +=1
        elif a[2]==i:
            a[2]+=1
        else:
            cur *=0
        a.sort(reverse=True)
        cur %=mod
    print(cur)
    return

def examF():
    return

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE(mod)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7
ans = 1
d = [0,0,0]
for x in a:
  tmp = 0
  for k in range(3):
    if x == d[k]:
      if tmp == 0:
        d[k] += 1
      tmp += 1
  ans *= tmp
  ans %= mod
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n=inp()
    a=inpl()
    ans=1
    num=[0,0,0]
    for i in range(n):
        cnt=0
        index=0
        for j in range(3):
            if num[j]==a[i]:
                cnt+=1
                index=j
        num[index]+=1
        if cnt==1:
            ans=ans%mod
            continue
        elif cnt==2:
            ans=(ans*2)%mod
        elif cnt==3:
            ans=(ans*3)%mod
        else:
            print(0)
            return
    print(ans%mod)

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
mod = 1000000007
ans = 1
tmp = [0] * n
for i in range(n):
    if a[i] == 0:
        ans *= 3 - tmp[0]
        tmp[0] += 1
    else:
        ans *= tmp[a[i]-1] - tmp[a[i]]
        ans %= mod
        tmp[a[i]] += 1

print(ans)

Solution (Python):
import numpy as np
MOD = 1000000007

n = int(input())
a = np.array(list(map(int, input().split())))
tails = np.full((3,), -1)
ind = np.arange(3)
res = 1
for aa in a:
    filt = tails == (aa-1)
    s = filt.sum()
    if s == 0:
        print(0)
        exit(0)
    res *= s
    res %= MOD
    i = ind[filt][0]
    tails[i] = aa
print(res)

Solution (Python):
n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
ans=1
B=[0,0,0]
for i in range(n):
  ct=0
  chk=False
  for j in range(3):
    if B[j]==A[i]:
      ct+=1
      if not chk:
        B[j]+=1
        chk=True
  ans=(ans*ct)%mod
print(ans)

Solution (Python):
import numpy as np

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

mod = 1000000007

A = np.zeros(N)

ans = 1

for i in range(N):
    hoge = D[i]
    if hoge == 0:
        ans *= int(3-A[hoge])
        A[hoge] += 1
    else:
        ans *= int(A[hoge-1]-A[hoge])
        A[hoge] += 1
    
    if ans > mod:
        ans = ans % mod

print(ans)

Solution (Python):
import sys; readline = sys.stdin.readline
from collections import deque


N = int(readline())
A = list(map(int, readline().split()))
P = 10**9 + 7


a = 1
state = [0, 0, 0]

for i in range(N):
    c = state.count(A[i]) 
    a *= c
    a %= P
    if c == 0:
        print(0)
        exit(0)
    state[state.index(A[i])] = A[i] + 1

print(a)

Solution (Python):
N = int(input())
A = input().split()

R = 0
G = 0
B = 0

Z = 1

for aa in A:
    a = int(aa)
    x = 0
    if a == R and a == G and a == B:
        x = x + 3
        R = R + 1
    elif a == R and a == G:
        x = x + 2
        R = R + 1
    elif a == R and a == B:
        x = x + 2
        R = R + 1
    elif a == G and a == B:
        x = x + 2
        G = G + 1
    elif a == R:
        x = x + 1
        R = R + 1
    elif a == B:
        x = x + 1
        B = B + 1
    elif a == G:
        x = x + 1
        G = G + 1
    Z = Z * x % 1000000007

print(Z)

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

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
b=[0,0,0]
c=1
for i in range(n):
    c*=b.count(a[i])
    c%=1000000007
    if b[0]==a[i]:
        b[0]+=1
    elif b[1]==a[i]:
        b[1]+=1
    else:
         b[2]+=1
print(c)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
cnt=[0]*3
ans=1
mod=10**9+7
for i in range(n):
	q=0
	if a[i]==cnt[0]:
		q+=1
	if a[i]==cnt[1]:
		q+=1
	if a[i]==cnt[2]:
		q+=1
	if a[i]==cnt[0]:
		cnt[0]+=1
	elif a[i]==cnt[1]:
		cnt[1]+=1
	else:
		cnt[2]+=1
	ans*=q
	ans%=mod
print(ans)

Solution (Python):
MOD = 1000000007

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

cnt = [-1, -1, -1]
ans = 1
for a in A:
    num = 0
    i = -1
    for j in range(3):
        if a == cnt[j] + 1:
            num += 1
            i = j
    if num == 0:
        ans = 0
        break
    ans *= num
    ans %= MOD
    cnt[i] = a

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [0] * N
dp[0] = 3
r = 1
g = 0
b = 0
if a[0] != 0:
  dp[0] = 0
for i in range(N - 1):
  f = 0
  if a[i + 1] == r:
    dp[i + 1] += dp[i]
    f = 0
  if a[i + 1] == g:
    dp[i + 1] += dp[i]
    f = 1
  if a[i + 1] == b:
    dp[i + 1] += dp[i]
    f = 2
  if f == 0: r += 1
  if f == 1: g += 1
  if f == 2: b += 1
  dp[i + 1] %= mod
print((dp[-1]) % mod)

Solution (Python):
MOD = int(1e9+7)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [0] * 3
    ans = 1
    for a in A:
        ans = (ans * cnt.count(a)) % MOD
        try:
            c = cnt.index(a)
        except ValueError:
            print(0)
            return
        cnt[c] += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
r = 1
n, m, l = 0, 0, 0
for A in As:
  if n == m == l == A:
    r = r*3%1000000007
    l += 1
  elif n < m == l == A:
    r = r*2%1000000007
    l += 1
  elif m < l == A:
    r = r*1%1000000007
    l += 1
  elif n == m == A < l:
    r = r*2%1000000007
    m += 1
  elif n < m == A < l:
    r = r*1%1000000007
    m += 1
  elif n == A < m:
    r = r*1%1000000007
    n += 1
  else:
    r = 0
print(r)