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):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
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 pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = LI()
    r = 1
    c = collections.defaultdict(int)
    c[0] = 3
    for b in a:
        r *= c[b]
        r %= mod
        c[b] -= 1
        c[b+1] += 1

    return r


print(main())

Solution (Python):

import sys
INF = float("inf")

MOD = 1000000007  


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

    return


def main():

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


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
lis = list(map(int,input().split()))
num = [0 for i in range(n)]
ans = 1
for nu in lis:
    if nu == 0:
        ans *= (3-num[0])
    else:
        ans *= (num[nu-1]-num[nu])
    ans %= 10 ** 9 + 7
    num[nu] += 1
print(ans)

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

Solution (Python):
def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)


import numpy
import scipy


"""
"""


N = gi()
tails = [0] * (N + 5)

tails[0] = 3
ans = 1
for i in range(N):
    a = gi()
    ans *= tails[a]
    ans %= MOD
    tails[a] -= 1
    tails[a + 1] += 1

print(ans)

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

A=list(map(int,input().split()))
l=[3]+[0]*(10**6)

ans=1
for i in range(len(A)):
    ans*=l[A[i]]
    l[A[i]]-=1
    l[A[i]+1]+=1
    ans%=(10**9+7)
    
print(ans)

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

inf = 10**9+7
occ = [0]*(N+1)

occ[0]=3

ans = 1

for i in range(0,N):
    ans=ans*(occ[A[i]]-occ[A[i]+1])%inf
    occ[A[i]+1]+=1

print(ans)

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

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

print(c)

Solution (Python):
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]
MOD = 10**9+7

N = INT()
A = MAP()

B = [0] * N
C = [0, 0, 0]
for i, a in enumerate(A):
	flg = False
	for j, c in enumerate(C):
		
		if a==c:
			B[i] += 1
			if not flg:
				C[j] += 1
				flg += 1




ans = 1
for b in B:
	ans *= b
	ans %= MOD

print(ans%MOD)

Solution (Python):
def main():
    n=int(input())
    a=list(map(int,input().split()))
    cnt=1
    now=[0,0,0]
    mod=10**9+7
    for i in a:
        cnt=(cnt*now.count(i))%mod
        for j in range(3):
            if now[j]==i:
                now[j]+=1
                break
    print(cnt)
main()

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(int)
    d[-1] = 3
    cnt = 1
    for v in a:
        cnt *= d[v-1]
        d[v] += 1
        d[v-1] -= 1
        cnt %= mod
    print(cnt)


if __name__ == '__main__':
    solve()

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

N = int(input())
A = list(map(int, input().split()))
cnt = [0]*N
p = 0
ans = 1
MOD = 10**9+7

for Ai in A:
    if Ai==0:
        cnt[Ai] += 1
        p += 1
    else:
        ans *= cnt[Ai-1]
        ans %= MOD
        cnt[Ai-1] -= 1
        cnt[Ai] += 1

if p==1:
    ans *= 3
elif p==2:
    ans *= 6
elif p==3:
    ans *= 6
else:
    ans = 0

print(ans%MOD)

Solution (Python):
N = int(input())
A = [int(_) for _ in input().split()]
mod = 10**9 + 7
cnt = [0] * (N + 1)
cnt[0] = 3
ans = 1
for a in A:
    ans *= cnt[a]
    ans %= mod
    cnt[a + 1] += 1
    cnt[a] -= 1
print(ans)

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


print(ans)

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
X=[-1,-1,-1]
ans=1
mod=10**9+7
for i in range(N):
    tmp=0
    if A[i]>i:
        ans=0
    for j in range(3):
        if X[j]==A[i]-1:
            tmp+=1
    for j in range(3):
        if X[j]==A[i]-1 or tmp==0:
            ans=tmp*ans
            ans%=mod
            X[j]+=1
            break
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
c1, c2, c3 = -1, -1, -1
ptn = 0
ptn_sum = 1

for i in range(n):
  if a[i] == c1+1:
    ptn += 1
  if a[i] == c2+1:
    ptn += 1
  if a[i] == c3+1:
    ptn +=1
    
  if a[i] == c1+1:
    c1 += 1
  elif a[i] == c2+1:
    c2 += 1
  elif a[i] == c3+1:
    c3 += 1  
  ptn_sum *= ptn
  ptn =0
print(ptn_sum%1000000007)

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

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


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

n = I()
A = LI()


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



print(ans)

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


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

n = I()
A = LI()


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



print(ans)

Solution (Python):
def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    N = int(f_i.readline())
    A = tuple(map(int, f_i.readline().split()))
    
    ans = 1
    xyz = [0, 0, 0]
    for A_i in A:
        cnt = xyz.count(A_i)
        if cnt == 0:
            print(0)
            break
        ans *= cnt
        ans %= mod
        xyz[xyz.index(A_i)] += 1
    else:
        print(ans)

solve()

Solution (Python):

import collections

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

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

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

Solution (Python):
n=int(input())
alist=[int(i) for i in input().split()]

zeros=0
answer=1
triple=[0,0,0]

for i in range(n):
    now=alist[i]
    if now==triple[0]:
        if now==triple[1]:
            if now==triple[2]:
                answer*=3
            else:
                answer*=2
        triple[0]+=1
    else:
        if now==triple[1]:
            if now==triple[2]:
                answer*=2
            triple[1]+=1
        else:
            if now==triple[2]:
                triple[2]+=1
            else:
                answer=0
    answer%=(1000000007)

print(answer)

Solution (Python):
n = int(input())
aa = list(map(int,input().split()))
x,y,z = [0]*(n+1),[0]*(n+1),[0]*(n+1)
tmp = [0]*n
for i,a in enumerate(aa):
  tmp[a]+=1
  if tmp[a]==1:
    x[i+1] = x[i]+1
    y[i+1] = y[i]
    z[i+1] = z[i]
  elif tmp[a]==2:
    x[i+1] = x[i]
    y[i+1] = y[i]+1
    z[i+1] = z[i]
  else:
    x[i+1] = x[i]
    y[i+1] = y[i]
    z[i+1] = z[i]+1
ans=1
for a,b,c,d in zip(x[:n],y[:n],z[:n],aa):
  ans = ans*[a,b,c].count(d)
print(ans%(10**9+7))

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

ptn = [3] + [0] * (max(a) + 1)
ans = 1
for i in a:
    ans *= ptn[i]
    ptn[i] -= 1
    ptn[i + 1] += 1

print(ans % 1000000007)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N = I()
A = III()

d = defaultdict(list)
for i in range(N):
    d[A[i]].append(i)

ans = 1
val = 3
for i in range(max(d.keys())+1):
    if len(d[i])>val:
        print(0)
        exit()
    else:
        if i==0:
            before = d[i]
            val = len(d[i])
        else:
            x = []
            for k in d[i]:
                x.append(sum([k>b for b in before]))
            z = 1
            for j,x1 in enumerate(x):
                z *= max(x1-j,0)
            if z==0:
                print(0)
                exit()
            else:
                ans *= z
                ans %= mod
            before = d[i]
m = 0
for x in d.values():
    if len(x)>=m:
        m = len(x)
if m==1:
    ans *= 3
    ans %= mod
else:
    ans *= 6
    ans %= mod

print(ans)

Solution (Python):
N = int(input())
arr = list(map(int, input().split()))
dp = [0,0,0]
ans = 1
mod = 1000000007

for i in range(N):
  cnt = dp.count(arr[i])
  for j in range(3):
    if dp[j]==arr[i]:
      dp[j] = arr[i]+1
      break  
  ans *= cnt
print(ans%mod)

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

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

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

Solution (Python):
n = int(input())
row = list(map(int, input().split()))
count = [3]+([0]*n)
ans = 1

for i in row:
    ans *= count[i]
    count[i] -= 1
    count[i+1] += 1

print(ans%1000000007)

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

x = [0 for i in range(N+10)]
x[0] = 3

mod = 1000000007

ans = 1

for a in A:
    ans *= x[a]
    ans %= mod
    if ans == 0:
        break
    x[a] = x[a] - 1
    x[a+1] = x[a+1] + 1


print(ans)

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

x[0]=3
ans=1

for i in range(n):
    if a[i]==0 and x[0]>0:
        ans*=x[0]
        ans%=mod
        x[0]-=1
        x[1]+=1
    
    elif a[i]==0 and x[0]==0:
        print(0)
        exit()
    
    else:
        if x[a[i]]>0:
            ans*=x[a[i]]
            ans%=mod
            x[a[i]]-=1
            x[a[i]+1]+=1
        
        else:
            print(0)
            exit()
        

print(ans)

Solution (Python):
import math


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


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


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

    pattern = [0 for _ in range(N + 1)]
    pattern[0] = 3

    ret = 1
    for a in A:
        ret *= pattern[a]
        pattern[a] -= 1
        pattern[a + 1] += 1
        
    return ret % 1000000007


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

Solution (Python):
M=1000000007

N = int(input())
A = [-1] + list(map(int,input().split()))

x = [0]*(N+1)
y = [0]*(N+1)
z = [0]*(N+1)
ans=1

for i in range(1,N+1):
    if A[i] == x[i-1] and A[i] == y[i-1] and A[i] == z[i-1]:
        ans = (ans * 3) %M
    elif A[i] == x[i-1] and A[i] == y[i-1]: 
        ans = (ans * 2) %M
    elif A[i] == y[i-1] and A[i] == z[i-1]: 
        ans = (ans * 2) %M
    elif A[i] == z[i-1] and A[i] == x[i-1]: 
        ans = (ans * 2) %M
    if A[i] == x[i-1]:
        x[i]=x[i-1]+1
        y[i]=y[i-1]
        z[i]=z[i-1]
    elif A[i] == y[i-1]:
        x[i]=x[i-1]
        y[i]=y[i-1]+1
        z[i]=z[i-1]
    elif A[i] == z[i-1]:
        x[i]=x[i-1]
        y[i]=y[i-1]
        z[i]=z[i-1]+1
    else:
        ans = 0
        break

print(ans)

Solution (Python):


MOD = 1000000007

def f(A):
    Q = [0]*3
    X = 1
    
    for a in A:
        Q2 = list(filter(lambda iq: iq[1] == a, enumerate(Q)))

        if len(Q2) == 0:
            return 0
        
        X *= len(Q2)
        X %= MOD
        

        Q[Q2[0][0]] += 1

    return X



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

    print(f(A))


if __name__ == '__main__':
    main()

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

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


def next_state(c, a, n_patterns):
    
    idx = -1
    for i in range(3):
        if c[i] == a:
            idx = i
            break
    if idx == -1:
        return -1, -1
    n_equals = 1
    n_equals += 1 if c[idx%3] == c[(idx + 1) % 3] else 0
    n_equals += 1 if c[idx%3] == c[(idx + 2) % 3] else 0
    c[idx%3] += 1
    n_patterns *= n_equals
    n_patterns %= 1000000007
    return c, n_patterns

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

Solution (Python):
import sys

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




MOD=10**9+7




import bisect

















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

Solution (Python):
import sys

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




MOD=10**9+7




import bisect

















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

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

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

print(ret)

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 1000000007


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

counts = [0] * (max(A) + 1)
ans = 1
for a in A:
    if a > 0:
        ans *= counts[a - 1]
        ans %= MOD
        counts[a - 1] -= 1
    counts[a] += 1
c0 = A.count(0)
if c0 == 1:
    print(ans * 3 % MOD)
elif c0 in (2, 3):
    print(ans * 6 % MOD)
else:
    print(0)

Solution (Python):
import sys

n = int(input())
a = list(map(int, input().split()))
 
ans = 1
r,g,b = 0,0,0
 
for x in a:
    ans *= [r,g,b].count(x)

    if r == x:r+=1
    elif g == x:g +=1
    elif b == x:b +=1
    else:
        print(0)
        sys.exit()
ans %= 1000000007 
print(ans)

Solution (Python):
mo = 1000000007
n = int(input())
A = [int(s) for s in input().split()]
maxLen = 0
for a in A:
    if a > maxLen:
        maxLen = a
maxLen += 1
memo = [[]for i in range(maxLen)]
for index,a in enumerate(A):
    memo[a].append(index)

def calc(cur,last):
    
    
    
    ans = 1
    minus = 0
    for i in cur:
        count = 0
        for j in last:
            if j < i:
                count += 1
        ans *= count-minus
        minus += 1
    return ans
    
    
    
    
    
    
    
    
    
    

memo.append([-1,-1,-1]) 
ans = 1
for i in range(maxLen):
    ans *= calc(memo[i],memo[i-1])
    ans %= mo
    
    

print(ans)

Solution (Python):
from collections import defaultdict
MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

cnt = defaultdict(int)
cnt[-1] = 3
ans = 1
for i in range(n):
    ans *= max(cnt[a[i] - 1] - cnt[a[i]], 0)
    ans %= MOD

    cnt[a[i]] += 1

print(ans)

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

ans = 1
r, g, b = 0, 0, 0

for x in a:
    ans *= [r, g, b].count(x)

    if r == x:r += 1
    elif g == x:g += 1
    elif b == x:b += 1

    else:
        print(0)
        exit()

ans %= 1000000007
print(ans)

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

Solution (Python):
def main():
  from collections import defaultdict
  N = int(input())
  A = list(map(int,input().split()))
  MOD = 1000000007
  c = defaultdict(int)
  c[0] = 3
  ans = 1
  for i in range(N):
    if not c[A[i]]:
      print(0)
      exit()
    ans *= c[A[i]]
    ans %= MOD
    c[A[i]] -= 1
    c[A[i]+1] += 1
  print(ans)
main()

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):
n = int(input())
a = list(map(int,input().split()))
now = [0,0,0]
mod = 10 ** 9 + 7
ans = 1
for x in a:
  tmp = 0
  for k in range(3):
    if now[k] == x:
      if tmp == 0:
        now[k] += 1
      tmp += 1
  ans *= tmp
  ans %= mod
print(ans)

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

MOD = 10 ** 9 + 7

ans = 1
count = 0
lst = [0] * (N + 1)
for a in A:
    if a == 0:
        ans *= (3 - count)
        count += 1
        lst[a] += 1
    else:
        ans *= lst[a - 1]
        lst[a] += 1
        lst[a - 1] -= 1
    ans %= MOD

print (ans)

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

Solution (Python):
mod = 1000000007

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

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

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
x = 1
l = [0] * n
for k in range(n):
    xl = l[a[k]]
    if a[k] == 0:
        xs = 3
    else:
        xs = l[a[k] - 1]
    if xs + 1 != xl:
        x = x * (xs - xl) % 1000000007
    l[a[k]] = l[a[k]] + 1
print(x)

Solution (Python):
import sys
bbn=1000000007





		
def main():
	n = int(input())
	aal = list(map(int, input().split()))
	cc=[0,0,0]
	total_count=1
	for nh in aal:
		nc = cc.count(nh)
		total_count = (total_count * nc ) % bbn
		if total_count == 0:
			return 0
		
		ii=cc.index(nh)
		
		cc[ii]+=1
		
	print(total_count)
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
mod = 10**9+7

ans = 1
n = [0,0,0]
for i in A:
    cnt = 0
    for ind ,j in enumerate(n):
        if i == j:
            cnt += 1
    for ind ,j in enumerate(n):
        if i == j:
            n[ind] += 1
            break
    ans = ans*cnt
    ans = ans % mod
print(ans)

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

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

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

N, *A = map(int, read().split())
mod = 10 ** 9 + 7

hats = [0] * 3
answer = 1

for i in range(N):
    answer *= hats.count(A[i])
    answer %= mod
    for j in range(3):
        if hats[j] == A[i]:
            hats[j] += 1
            break

print(answer)

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

N, *A = map(int, read().split())
mod = 10 ** 9 + 7

hats = [[0] * 3 for _ in range(N + 1)]
answer = 1

for i in range(N):
    answer *= hats[i].count(A[i])
    answer %= mod
    flag = True
    for j in range(3):
        if hats[i][j] == A[i] and flag:
            hats[i + 1][j] = A[i] + 1
            flag = False
        else:
            hats[i + 1][j] = hats[i][j]

print(answer)

Solution (Python):
MOD = 1000000007

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

vec = [0, 0, 0]
num = 1

for a in A:
    idx = [i for i, x in enumerate(vec) if x == a]
    if len(idx) == 0:
        print(0)
        exit()
    num = (num * len(idx)) % MOD
    vec[idx[0]] += 1

print(num)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
colors = [0,0,0]
ans = 1
for i in range(N):
    ans = (ans * colors.count(A[i])) % mod
    for j in range(3):
        if colors[j] == A[i]:
            colors[j] += 1
            break
print(ans)

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

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

ans = 1
numRGBs = [0] * 3
for A in As:
    num = 0
    for i in range(3):
        if numRGBs[i] == A:
            num += 1
            if num == 1:
                numRGBs[i] += 1
    ans *= num
    ans %= MOD

print(ans)

Solution (Python):
from collections import Counter

mod = 10**9 + 7

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

c = Counter()
c[-1] = 3
ans = 1
for i in range(N):
    ans *= c[A[i]-1] - c[A[i]]
    c[A[i]] += 1
ans %= mod
print(ans)

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

Solution (Python):

from itertools import combinations
import sys
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
a = [int(item) for item in input().split()]

rgb = [-1, -1, -1]
ans = 1
for item in a:
    cnt = rgb.count(item - 1)
    if cnt == 0:
        print(0)
        exit()
    rgb[rgb.index(item-1)] = item
    ans *= cnt
    ans %= MOD
print(ans)

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

Solution (Python):
N = int(input())
A = map(int, input().split())
MOD = 1000000007
ans = 1
cnt = [3 if i == 0 else 0 for i in range(N+1)] 

for a in A:
  ans = ans * cnt[a] % MOD
  if ans == 0:
    break
  cnt[a] -= 1 
  cnt[a+1] += 1
  
print(ans)

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

Solution (Python):
n , *a_s = map(int,open(0).read().split())
tmp = [3] + [0 for _ in range(n+1)]
ans = 1
for a in a_s:
  ans = ans * tmp[a] % 1000000007
  tmp[a] -= 1
  tmp[a+1] += 1
  
print(ans)

Solution (Python):

n = int(input())
num = [ int(v) for v in input().split() ]
counter = [3] + [ 0 for i in range(n) ]
ans = 1
mod = 10**9+7
for i in num:
    ans *= counter[i]
    ans %= mod
    counter[i] -= 1
    counter[i+1] += 1

print(ans)

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

c = [0]*3

a = 1

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * 3
num = 0
ans = 1

for i in range(n):
	if cnt.count(a[i])  == 0:
		ans = 0
		break
	else:
		ans = (ans * cnt.count(a[i])) % 1000000007
		cnt[cnt.index(a[i])] += 1
	num = 0

print(ans)

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

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

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
ans = 1


cnt = [3 if i == 0 else 0 for i in range(N+1)]

for a in A:
    ans = ans * cnt[a] % mod
    if ans == 0:
        break
    cnt[a] -= 1
    cnt[a+1] += 1

print(ans)