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()))
P = 1000000007
dp = [0] *(N + 1)
dp[0] = 1
color = [0, 0, 0]
for i in range(N):
    count = 0
    check= True
    for j in range(3):
        if color[j] == A[i]:
            count += 1
            if check:
                color[j] += 1
                check = False
    dp[i + 1] += (dp[i] * count)%P
print(dp[-1])

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

rgb = [0 for i in range(3)]

count = 1
m = 1000000007

for i in range(n):
    a = arr[i]
    temp = 0
    hoge = -1
    for j in range(3):
        if rgb[j] == a:
            hoge = j
            temp += 1
    rgb[hoge] += 1
    if temp == 0:
        count = 0
        break
    else:
        count *= temp
        count = count%m


print(count)

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

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

cnt = 1
last = [-1,-1,-1]

for a in A:
    cnt *= last.count(a-1)
    cnt %= MOD
    if cnt == 0:
        break
    last[last.index(a-1)] += 1

print(cnt)

Solution (Python):
import sys
from itertools import combinations, permutations

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]

    mod = 1000000007
    rgb = [0, 0, 0]
    count = 1
    for i in range(N):
        a = A[i]
        if rgb[0] == a:
            if rgb[1] == a:
                if rgb[2] == a:
                    count *= 3
                    count %= mod
                else:
                    count *= 2
                    count %= mod
            rgb[0] += 1
        else:
            if rgb[1] == a:
                if rgb[2] == a:
                    count *= 2
                    count %= mod
                rgb[1] += 1
            else:
                if rgb[2] == a:
                    rgb[2] += 1
                else:
                    count = 0
                    break
    
    print(count)
                    
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
LARGE = 1000000007


def solve(n, a_list):

    x = -1
    y = -1
    z = -1
    res = 1

    for i in range(n):
        c = 0
        a = a_list[i]
        if x == a - 1:
            c += 1
        if y == a - 1:
            c += 1
        if z == a - 1:
            c += 1
        if x == a - 1:
            x += 1
        elif y == a - 1:
            y += 1
        else:
            z += 1
        res *= c
        res %= LARGE
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(6, [0, 1, 2, 3, 4, 5]) == 3
    assert solve(3, [0, 0, 0]) == 6


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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
A =list(map(int,input().split()))
a=1
b=[0,0,0]
for i in A:
    t=b.count(i)
    if i==b[0]:
        b[0]+=1
    elif i==b[1]:
        b[1]+=1
    elif i==b[2]:
        b[2]+=1
    a=a*t%(10**9+7)
print(a)

Solution (Python):

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

R = 0
G = 0
B = 0
ans = -1
count = 1
for i,a in enumerate(A):
    if i == 0:
        if a != 0:
            ans = 0
            break
        else:
            R = 1
            count*=3
    else:
        if R == a and G == a and B == a:
            count*=3
            R+=1
        elif R == a and G == a:
            count*=2
            R+=1
        elif R == a and B == a:
            count*=2
            R+=1
        elif G == a and B == a:
            count*=2
            G+=1
        elif R == a:
            R+=1
        elif G == a:
            G+=1
        elif B == a:
            B+=1
        else:
            ans = 0
            break
        
            
if ans == 0:
    print(ans)
else:
    ans = count
    print(ans%mod)

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

ans=1
b = [-1,-1,-1]
for i in a:
    flag = True
    count=0
    for j in range(3):
        if b[j] == i - 1:
            if flag:
                b[j] += 1
                flag=False
            count +=1
    ans = ans * count % 1000000007
print(ans)

Solution (Python):
MOD = 1000000007
n = int(input())
a = list(map(int, input().split()))
zero = a.count(0)

if zero == 1:
	ans = 3
elif 2 <= zero <= 3:
	ans = 6
else:
	ans = 0

cnt = [0 for _ in range(n)]
for x in a:
	cnt[x] += 1
	if cnt[x] > 3:
		ans = 0
	if x > 0:
		ans *= cnt[x-1]
		ans %= MOD
		cnt[x-1] -= 1

print(ans)

Solution (Python):

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

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

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    d = collections.defaultdict(int)
    t = 1
    for i in range(n):
        if a[i] == 0:
            t *= 3 - d[0]
            d[a[i]] += 1
        else:
            t *= d[a[i]-1] - d[a[i]]
            d[a[i]] += 1
        t %= mod
    print(t)


if __name__ == '__main__':
    solve()

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

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

Solution (Python):

from collections import defaultdict


def getlist():
	return list(map(int, input().split()))

con = 10 ** 9 + 7

def main():
	N = int(input())
	A = getlist()
	RGB = [0, 0, 0]
	ans = 1
	for i in range(N):
		cnt = 0
		jud = "No"
		for j in range(3):
			if A[i] == RGB[j]:
				cnt += 1
				if jud == "No":
					RGB[j] += 1
					jud = "Yes"
		ans = (ans * cnt) % con

	print(ans)

if __name__ == '__main__':
	main()

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

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

print(ans)

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

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

N = int(readline())
A = list(map(int, readline().split()))
MOD = 1000000007

def calc(A):
    CA = Counter(A)
    if max(CA.values()) > 3:
        return 0
    
    pop = [0]*(N+3)
    pop[-1] = 3
    
    res = 1
    for a in A:
        if pop[a-1] <= 0:
            return 0
        res = (res*pop[a-1]) %MOD
        pop[a-1] -= 1
        pop[a] += 1
        
    
    
        
    return res
        

print(calc(A))

Solution (Python):
MOD=1000000007
N=int(input())
ls=[int(s) for s in input().split()]
RGB=[0,0,0]
ans=1
for i in range(N):
  if ls[i] in RGB:
    x=RGB.count(ls[i])
    ans=(ans*x)%MOD
    y=RGB.index(ls[i])
    RGB[y]+=1
  else:
    ans=0
    break
print(ans)

Solution (Python):


import os
import sys


def main():
    N = read_int()
    A = read_ints()
    print(solve(N, A))


MOD = 1000000007


def solve(N, A):
    c = 1
    nums = [0, 0, 0]

    for a in A:
        z = nums.count(a)
        if z == 0:
            return 0
        c *= z
        c %= MOD
        nums[nums.index(a)] = a + 1

    return c




DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


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):
import sys

MOD = 10 ** 9 + 7

def main():
    n, *a = map(int, sys.stdin.read().split())

    res = 1
    rgb = [0, 0, 0]
    for i in range(n):
        cur = a[i]
        c = rgb.count(cur)
        res = res * c % MOD
        if cur == rgb[0]:
            rgb[0] += 1
        elif cur == rgb[1]:
            rgb[1] += 1
        elif cur == rgb[2]:
            rgb[2] += 1
    print(res)

if __name__ == '__main__':
    main()

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:
  ans*=color.count(i)
  ans%=mod
  for j in range(3):
    if color[j]==i:color[j]+=1;break
print(ans%mod)

Solution (Python):
from sys import stdin


def input():
    return stdin.readline()[:-1]


def intput():
    return int(input())


def sinput():
    return input().split()


def intsput():
    return map(int, sinput())




n = intput()

a = list(intsput())

rgb = [0, 0, 0]

ans = 1
for i in range(n):
    x = a[i]
    cnt = 0
    placed = False
    for j in range(3):
        if rgb[j] == x:
            if not placed:
                rgb[j] += 1
                placed = True
            cnt += 1
        
    ans *= cnt
    ans %= 10 ** 9 + 7

print(ans)

Solution (Python):
from collections import defaultdict

N = int(input())
A = [int(i) for i in input().split()]

mod = 10 ** 9 + 7

d = defaultdict(int)
d[-1] = 3

ret = 1
for a in A :
    ret = ret * d[a-1] % mod
    d[a-1] -= 1
    d[a] += 1
    
print(ret)

Solution (Python):
mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
cnt = [0, 0, 0]
ans = 1
for a in A:
    c = 0
    for j in range(3):
        if cnt[j] == a:
            c+=1
            if c == 1:
                cnt[j]+=1
    ans*=c
    ans%=mod
print(ans)

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

m = 1000000007
b = [-1,-1,-1]
ans = 1

for i in range(n):
    ans *= b.count(a[i]-1)
    ans%=m
    if ans ==0:
        print(0)
        exit()
    for j in range(3):
        if b[j]==a[i]-1:
            b[j]+=1
            break

print(ans%m)

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

N = int(input())

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

lis = [0,0,0]
ans = 1

for i in range(N):

    na = A[i]
    ind = 0
    nn = 0

    for j in range(3):
        if lis[j] == na:
            nn += 1
            ind = j

    lis[ind] += 1

    if nn == 0:
        ans *= 0

    elif nn == 2:
        ans *= 2
    elif nn == 3:
        ans *= 3

    ans %= mod
    

print (ans % mod)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
f = [0] * 3
ans = 1
m = 1000000007
for x in a:
  c = 0
  for y in f:
    if x == y:
      c += 1
  ans = ans * c % m
  for i in range(3):
    if f[i] == x:
      f[i] += 1
      break
print(ans)

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

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

remain = 3
s = [0,0,0]
ans = 1
for i in a:
    k = s.count(i)
    ans *= s.count(i)
    ans %= mod
    if k == 0:
        break
    s[s.index(i)] += 1

print(ans)

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):
n = int(input())
A = list(map(int, input().split()))
x = 0
y = 0
z = 0
ans = 1
for i in range(n):
  a = A[i]
  ans *= int(a==x) + int(a==y) + int(a==z)
  if a == x:
    x += 1
  elif a == y:
    y += 1
  elif a == z:
    z += 1
  else:
    print(0)
    exit()
print(ans%(10**9+7))

Solution (Python):
mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))
p = [-1,-1,-1]
ans = 1
for i in range(N):
    a = A[i]
    ans *= p.count(a-1)
    ans %= mod
    for j in range(3):
        if p[j]==a-1:
            p[j] = a
            break
print(ans)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

a = l()

al = []

co = 1

for i in range(n):
    if a[i] == 0:
        co *= max(0,(3-len(al)))
        al.append(0)
    else:
        on = 0
        flag = True
        for j in range(len(al)):
            if al[j] == a[i]-1:
                on += 1
                if flag == True:
                    al[j] += 1
                    flag = False
        co *= on
        co %= mod
print(co)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
count = [0 for i in range(N)]
count[-1] = 3

MOD = 1000000007
ways = 1
for n in A:
    ways *= count[n-1]
    count[n-1] -= 1
    count[n] += 1
    ways %= MOD
print(ways)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
color = [0,0,0]
ans = 1
for i in a:
  mini = 0
  al = 0
  for key,j in enumerate(color):
    if i == j:
      if al == 0:
        al = 1
        color[key] += 1
      mini += 1
  ans = (ans * mini) % mod
print(ans)

Solution (Python):
import numpy as np

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

ans = 1
count = np.zeros(N + 1, dtype="int")
count[0] = 3

for i in A:
    ans *= max(0, count[i] - count[i + 1])
    ans %= 1000000007
    count[i + 1] += 1

print(ans)

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

D = [0] * 3

ans = 1
for i in A:
  c = 0
  for j in range(3):
    if i == D[j]:
      if c == 0:
        D[j] += 1
      c += 1
  ans = ans * c % MOD

print(ans)

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

res = 1
tank = [0,0,0]

for e in a:
    cnt = 0
    idx = -1
    if tank[0] == e:
        cnt += 1
        idx = 0
    if tank[1] == e:
        cnt += 1
        idx = 1       
    if tank[2] == e:
        cnt += 1
        idx = 2
    
    if cnt == 0:
        print(0)
        exit()
    
    res = res*cnt%mod
    tank[idx] += 1

print(res)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    d = [0,0,0]
    ans = 1
    for i in a:
        ans *= d.count(i)
        ans %= mod
        if ans == 0:
            break
        for j in range(3):
            if d[j] == i:
                d[j] += 1
                break
    print(ans)
    return


if __name__ == "__main__":
    solve()

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

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

mod=1000000007

DP=[0,0,0]
ANS=1

for a in A:
    ANS=ANS*DP.count(a)%mod
    if ANS==0:
        print(0)
        sys.exit()
    x=DP.index(a)
    DP[x]+=1

print(ANS)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,*A = map(int,read().split())

MOD = 10 ** 9 + 7

A = [x + 1 for x in A]

counter = [0] * (N+100)
counter[0] = 3
answer = 1
for x in A:
    answer *= counter[x-1]
    counter[x-1] -= 1
    counter[x] += 1
    answer %= MOD

print(answer)

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
mod=10**9+7
ans=1
rgb=[0]*3
for i in range(n):
    f=0
    for j in range(3):
        if l[i]==rgb[j]:
            if f==0:
                rgb[j]+=1
            f+=1
    ans*=f
    ans%=mod
print(ans)

Solution (Python):
def main():
    mod=1000000007
    n=int(input())
    A=list(map(int,input().split()))
    RGB=[0]*3
    ans=1
    for a in A:
        tmp=0
        for k in RGB:
            if a==k:
                tmp+=1
        ans*=tmp
        ans%=mod
        for i,k in enumerate(RGB):
            if a==k:
                RGB[i]+=1
                break
        else:
            return 0
    return ans
    
if __name__=='__main__':
    print(main())

Solution (Python):
import sys

def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy

def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d

MOD = 10**9 + 7

def main():
    n = getN()
    nums = getlist()
    ans = 1
    bc, bv, bb = -1, -1, -1
    for num in nums:
        tmp = 0
        added = 0
        if num == bc + 1:
            tmp += 1
            if not added:
                bc += 1
                added = 1

        if num == bv + 1:
            tmp += 1
            if not added:
                bv += 1
                added = 1

        if num == bb + 1:
            tmp += 1
            if not added:
                bb += 1
                added = 1

        ans *= tmp
        ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
P = 10**9+7
ans = 1
X = [0, 0, 0]
for a in A:
    c = X.count(a)
    ans = ans * c % P
    if X[0] == a:
        X[0] += 1
    elif X[1] == a:
        X[1] += 1
    else:
        X[2] += 1
print(ans)

Solution (Python):

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
AA = inpl()

cnts = [0]*(N+1)
cnts[-1] = 3

ans = 1
for a in AA:
    ans *= (cnts[a-1] - cnts[a])
    ans %= mod
    cnts[a] += 1


print(ans)

Solution (Python):


import sys
readline = sys.stdin.readline 

n = int(input())

a = [int(i) for i in readline().split()]


MOD = 1000000007

ans = 1
res = [0,0,0]

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

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)
    ans %= 1000000007
    if r == x:r+=1
    elif g == x:g +=1
    elif b == x:b +=1
    else:
        print(0)
        exit()

print(ans)

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)