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
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


def main():

    inf = 10 ** 18
    mod = 10 ** 9 + 7

    n = ir()
    a = lr()
    dp = [[0, 0, 0] for i in range(n+1)]
    for i in range(n):
        now = a[i]
        if dp[i][0] == now:
            dp[i+1][0] = dp[i][0]+1
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]
        elif dp[i][1] == now:
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]+1
            dp[i+1][2] = dp[i][2]
        elif dp[i][2] == now:
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]+1
        else:
            print(0)
            sys.exit()

    ans = 1
    for i in range(n):
        x,y,z = dp[i]
        now = a[i]
        if x == now and y == now and z == now:
            ans *= 3
        elif (x == now == y) or (y == now == z) or (z == now == x):
            ans *= 2
        ans %= mod
    print(ans)




    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
counter=[0 for i in range(n+1)]
counter[0]=3
ans=1
for i in range(n):
    ans=(ans*(counter[lis[i]]-counter[lis[i]+1]))%mod
    counter[lis[i]+1]+=1
print(ans%mod)

Solution (Python):
import sys
from collections import Counter as cc
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    mod = 10**9 + 7
    n = ii()
    a = li()
    t = [0]*(n)
    ans = 1
    for i in range(n):
        if a[i] == 0:
            tmp = 3
        else:
            tmp = t[a[i]-1]
        ans *= tmp-t[a[i]]
        ans %= mod
        t[a[i]] += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline
 
N=int(input())
A=list(map(int,input().split()))
color1 = -1
color2 = -1
color3 = -1
 
m = 10**9+7
patern = 1
 
for a in A:
    if color1 == a-1 and color2 == a-1 and color3 == a-1:
        patern = (patern * 3)%m
        color1 = a
 
    elif (color1 != a-1 and color2 == a-1 and color3 == a-1):
        patern = (patern * 2)%m
        color2 = a
 
    elif (color1 == a-1 and color2 == a-1 and color3 != a-1):
        patern = (patern * 2)%m
        color1 = a
    elif (color1 == a-1 and color2 != a-1 and color3 != a-1):
        color1 = a
 
    elif (color1 != a-1 and color2 == a-1 and color3 != a-1):
        color2 = a
 
    elif (color1 != a-1 and color2 != a-1 and color3 == a-1):
        color3 = a
 
    elif (color1 != a-1 and color2 != a-1 and color3 != a-1):
        patern = 0
        break
print(patern)

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

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


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*N
    ans = 3
    for a in A:
        if a == 0:
            if B[a] == 1:
                ans *= 2
        else:
            ans *= B[a-1] - B[a]
        B[a] += 1
        if 3 < B[a] or (a != 0 and B[a-1] < B[a]):
            ans = 0
            break
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

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

ctr = [0, 0, 0]
ans = 1
for a in X:
    ptn = sum(a == v for v in ctr)
    ans = ans * ptn % MOD

    if ans == 0:
        break

    for i in range(3):
        if ctr[i] == a:
            ctr[i] += 1
            break

print(ans)

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    """
    N = read_int()
    A = read_ints()
    T = [0, 0, 0]
    answer = 1
    modulo = 1000000007
    for a in A:
        if a not in T:
            return 0
        answer = (answer*T.count(a))%modulo
        T[T.index(a)] += 1
    return answer


if __name__ == '__main__':
    print(solve())

Solution (Python):
import sys

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

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

if A[0]!=0:
    print(0)
    sys.exit()

for i in range(1,n):
    count=status.count(A[i])
    if count==0:
        print(0)
        sys.exit()
    
    ans=(ans*count)%p
    status[status.index(A[i])]+=1

print(ans)

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

Solution (Python):



mod = 10**9+7
def main():
	ans =1
	n = int(input())
	arr = list(map(int , input().split()))
	col=[0 for i in range(0 , 6)]
	for i in range(0 , n):
		cnt , cur =0 , -1
		if arr[i]==col[0]:
			cnt = cnt+1
			cur = 0
		if arr[i]==col[1]:
			cnt = cnt+1
			cur = 1
		if arr[i]==col[2]:
			cnt = cnt+1
			cur = 2
		if cur ==-1:
			print(0)
			exit()
		col[cur]=col[cur]+1
		ans = (ans*cnt)%mod
		ans = ans%mod
	print(ans)

if __name__ =="__main__":
	main()

Solution (Python):
mod = 10**9+7
def main():
	ans =1
	n = int(input())
	arr = list(map(int , input().split()))
	col=[0 for i in range(0 , 6)]
	for i in range(0 , n):
		cnt , cur =0 , -1
		if arr[i]==col[0]:
			cnt = cnt+1
			cur = 0
		if arr[i]==col[1]:
			cnt = cnt+1
			cur = 1
		if arr[i]==col[2]:
			cnt = cnt+1
			cur = 2
		if cur ==-1:
			print(0)
			exit()
		col[cur]=col[cur]+1
		ans = (ans*cnt)%mod
		ans = ans%mod
	print(ans)

if __name__ =="__main__":
	main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    R = 0
    G = 0
    B = 0
    ans = 1
    for a in A:
        if a == R == G == B:
            ans *= 3
            ans %= MOD
            R += 1
        else:
            if a == R == G:
                ans *= 2
                ans %= MOD
                R += 1
            elif a == G == B:
                ans *= 2
                ans %= MOD
                G += 1
            elif a == B == R:
                ans *= 2
                ans %= MOD
                B += 1
            else:
                if a == R:
                    R += 1
                elif a == G:
                    G += 1
                elif a == B:
                    B += 1
                else:
                    print(0)
                    sys.exit()
    print(ans % MOD)


if __name__ == '__main__':
    main()

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

Solution (Python):
MOD = 10**9 + 7
def solve(n, a):
    dp = [3] + [0] * n
    res = 1
    for x in a:
        res = res * dp[x] % MOD
        if res == 0:
            break
        dp[x] -= 1
        dp[x+1] += 1
    return res

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

Solution (Python):
import sys

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

G={k:0 for k in range(-1,max(A)+1)}
G[-1]=3

X=1
for a in A:
    X*=G[a-1]-G[a]
    X%=M
    G[a]+=1
print(X)

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

ans=1
d={}
for i in range(N+1):
	d[i]=0

d[0]=3

for a in A:
	ans*=d[a]
	d[a]-=1
	d[a+1]+=1
	if ans>=10**9+7:
		ans=ans%(10**9+7)


print(ans)

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

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


if __name__ == '__main__':
    main()

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

t=[0,0,0]
ans=1

for i in range(n):
    now=A[i]
    cnt=0
    for q in range(3):
        if t[q]==now:
            cnt+=1
    ans=ans*cnt%mod
    for q in range(3):
        if t[q]==now:
            t[q]+=1
            break

print(ans)

Solution (Python):
from collections import defaultdict
def solve():
  d = defaultdict(lambda: 0)
  N = int(input())
  A = list(map(int, input().split()))
  mod = 10**9+7
  d[0] = 3
  ans = 1
  for i in range(N):
    if d[A[i]]==0:
      return 0
    ans *= d[A[i]]
    ans %= mod
    d[A[i]] -= 1
    d[A[i]+1] += 1
  return ans
print(solve())

Solution (Python):

n = int(input())
nums = map(int, input().split())
MOD = 1000000007
ans = 1
cnt = [3 if i == 0 else 0 for i in range(n + 1)]

for num in nums:
    ans = ans * cnt[num] % MOD
    if ans == 0:
        break
    cnt[num] -= 1
    cnt[num+1] += 1

print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    a = list(map(int, readline().split()))

    cnt = [0] * 3
    ans = 1

    for x in a:
        p = cnt.count(x)
        if p == 0:
            return print(0)
        ans *= p
        ans %= MOD
        cnt[cnt.index(x)] += 1

    print(ans)


if __name__ == '__main__':
    main()

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

cnts = [0,0,0]
sames = 0
ind = -1
res = 1
for a in a_list:
    for i, cnt in enumerate(cnts):
        if cnt == a: 
            sames += 1
            ind = i
    res *= sames
    res %= MOD
    cnts[ind] += 1
    sames = 0

print(res)

Solution (Python):
def main():
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split()))
    hat_cnt = [0, 0, 0]
    ans = 1
    for a in A:
        t = len([c for c in hat_cnt if c == a])
        if t == 0:
            ans = 0
            break
        ans *= t
        ans %= MOD
        for i in range(len(hat_cnt)):
            if hat_cnt[i] == a:
                hat_cnt[i] += 1
                break
    print(ans)


if __name__ == '__main__':
    main()

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

ans =1
mod = 10**9+7
row = [0] *3
for i in range(N):
    
    ans *=row.count(A[i])
    ans %=mod
    for j in range(3):
        if row[j]==A[i]:
            row[j]+=1
            break
    

        
print(ans%mod)

Solution (Python):
MOD = 10**9 + 7
n = int(input())
x, y, z = 0, 0, 0
ans = 1
for a in map(int, input().split()):
    if a == x:
        if x != y:
            x += 1
        elif y != z:
            ans = ans * 2 % MOD
            y += 1
        else:
            ans = ans * 3 % MOD
            z += 1
    elif a == y:
        if y != z:
            y += 1
        else:
            ans = ans * 2 % MOD
            z += 1
    elif a == z:
        z += 1
    else:
        ans = 0
print(ans)

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

Solution (Python):
import sys
input = sys.stdin.readline
mod = 10**9 + 7

def main():
    n = int(input())
    A = list(map(int, input().split()))
    candidates = [0] * (n+1)
    candidates[0] = 3
    ans = 1

    for a in A:
        ans *= candidates[a]
        ans %= mod
        candidates[a] -= 1
        candidates[a+1] += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = LIST()
ans = 1
r = 0
g = 0
b = 0

for x in a:
    ans = ans * ( (r == x) + (g == x) + (b == x) ) % (10**9+7)
    if r == x:
        r += 1
    elif g == x:
        g += 1
    else:
        b += 1
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
b=[0,0,0]
ans=1
mod=1000000007
for i in range(n):
    aa=a[i]
    tmp=0
    flg=False
    for j in range(3):
        if aa==b[j]:
            tmp+=1
            if flg==False:
                b[j]+=1
                flg=True
    ans*=tmp
    ans%=mod
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    A=list(mi())
    MOD = 1000000007

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

    ans %= MOD
    print(ans)




if __name__ == "__main__":
    main()

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

mod = int(1e9+7)

CNT = [0] * (N+10)
CNT[-1] = 3
ans = 1
for a in A:
  CNT[a] += 1
  ans *= CNT[a-1]
  ans %= mod
  CNT[a-1] -= 1

print(ans)

Solution (Python):
import sys

input = sys.stdin.readline


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

    P = 10 ** 9 + 7
    num = [0, 0, 0]
    ans = 1
    for a in A:
        cnt = num.count(a)
        if cnt == 0:
            ans = 0
            break
        ans = (ans * cnt) % P
        num[num.index(a)] += 1

    print(ans)


if __name__ == "__main__":
    main()

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

for i in a:
  count=0
  flg=True
  for j in range(3):
    if rbg[j]==i:
      count+=1
      if flg:
        rbg[j]+=1
        flg=False
  ans*=count
  ans%=MOD
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)

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
P = 1000000007

lst = [0,0,0]
rlt = 1

for i in range(N):
  cnt = lst.count(As[i])
  rlt *= cnt
  rlt %= P
  for j in range(3):
    if lst[j] == As[i]:
      lst[j] += 1
      break
      
print(rlt)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
ans = 1
M = 10**9+7
s = [0,0,0]
for i,num in enumerate(a):
    if num not in s:
        ans = 0
        break
    ans *= sum(item==num for item in s)
    ans %= M
    s[s.index(num)] += 1
print(ans)

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

Solution (Python):

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

L = 1000000007

state = [0,0,0]

M = [0,0,0]
for a in A:
    t = None
    n = 0
    for i,s in enumerate(state):
        if s == a:
            t = i
            n += 1
    if n == 0:
        break
    M[n-1] += 1
    state[t] += 1

if n > 0:
    x = 2**30 % L
    y = 3**19 % L


    k = M[1] % x
    l = M[2] % y
    r = 2**k * 3**l % L
    print(r)
else:
    print(0)

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



xyz = [[0]*(N+1) for _ in range(3)]
for i in range(N):
    is_added = False
    for j in range(3):
        if xyz[j][i] == A[i] and not is_added:
            xyz[j][i+1] = xyz[j][i] + 1
            is_added = True
        else:
            xyz[j][i+1] = xyz[j][i]




ans = 1
for i in range(N):
    cnt = 0
    for j in range(3):
        if xyz[j][i] == A[i]:
            cnt += 1
    ans = ans*cnt % MOD
print(ans)

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

ans = 1
MOD = 1000000007
cnt = [0 for _ in range(N+1)]
cnt[0] += 3

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

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

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

Solution (Python):

MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
count = [0]*N+[3]
used = [0]*(N+1)
ans = 1
for x in A:
    ans = (ans*(count[x-1]-used[x-1]))%MOD
    count[x] += 1
    used[x-1] += 1
print(ans)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
cnt = [0]*(n+1)
cnt[-1] = 3
mod = 1000000007
ans = 1
for i in range(n):
    ans *= cnt[a[i]-1]
    ans %= mod
    cnt[a[i]-1] -= 1
    cnt[a[i]] += 1
print(ans)

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

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

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

res = 1
for i,a in enumerate(A):
  res *= cnt[a]
  res %= MOD
  cnt[a] -= 1
  cnt[a+1] += 1

print(res % MOD)

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

ans = 1
for i in range(N):
    ans *= cnt.count(A[i])
    ans %= mod
    if ans == 0:
        break
    cnt[cnt.index(A[i])] += 1

print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
mod = 10**9+7
x,y,z=0,0,0
ans=1
for a in A:
  ans*=[x,y,z].count(a)
  ans%=mod
  if x==a:
    x+=1
  elif y==a:
    y+=1
  else:
    z+=1
print(ans)

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

N = int(input())
A = list(map(int, input().split()))
ans = 1
MOD = 10**9+7
r, g, b = 0, 0, 0

for Ai in A:
    cnt = 0
    
    if r==Ai:
        cnt += 1
    
    if g==Ai:
        cnt += 1
    
    if b==Ai:
        cnt += 1
        
    ans *= cnt
    ans %= MOD
    
    if r==Ai:
        r += 1
    elif g==Ai:
        g += 1
    else:
        b += 1
    
print(ans)

Solution (Python):

def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    MOD = 10**9 + 7
    MAX_N = 10**5

    count_arr = [0]*(MAX_N+1)
    count_arr[0] = 3

    ans = 1
    for a in A:
        ans *= count_arr[a]
        ans %= MOD

        count_arr[a] -= 1
        count_arr[a+1] += 1

    print(ans)

if __name__ == "__main__":
    main()

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

RGB = [0, 0, 0]

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

print(ans)

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

Solution (Python):



def main():
    mod = 10**9+7
    N = int(input())
    A = list(map(int, input().split()))
    C = [0] * 3
    ret = 1
    for i in range(N):
        ret *= C.count(A[i])
        ret %= mod
        for j in range(3):
            if C[j]==A[i]:
                C[j]+=1
                break
    print(ret)

if __name__ == '__main__':
    main()

Solution (Python):
N,*A = map(int, open(0).read().split())
group = [0] * 3
ans = 1
for x in A:
    ans = (ans*group.count(x)) % 1000000007
    if ans == 0:
        print(0)
        break
    else:
        group[group.index(x)] += 1
else:
    print(ans)

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

ans=1
for i in range(N):
    cnt=0
    idx=-1
    for j in range(3):
        if A[i]==B[j]:
            cnt+=1
            idx=j
    ans=ans*cnt
    ans=ans%mod
    B[idx]+=1
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
MOD = 1000000007
cnt = [0,0,0] 
ans = 1 
for a in A:
    idx = []
    for i in range(3):
        if cnt[i] == a: 
            idx.append(i)
    if len(idx)==0: 
        print(0)
        exit()
    cnt[idx[0]]+=1 
    ans *= len(idx) 
    ans %= MOD
print (ans)

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

mod = 1000000007

cnt = [0] * 3
ans = 1

for i in range(n):
    count = 0
    minj = 4
    for j in range(3):
        if hats[i] == cnt[j]:
            count += 1
            minj = min(minj, j)
    if count == 0:
        ans = 0
        break
    cnt[minj] += 1

    ans = ans * count % mod

print(ans)

Solution (Python):
import sys






def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))




def main():
	n=II()
	A=LI()
	B=[0]*(n+1)
	ans=1
	B[0]=3

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

	print(ans)








if __name__ == "__main__":
	main()

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

ans=1

for i in range(n):
    ans*=col[a[i]]
    col[a[i]]-=1
    col[a[i]+1]+=1
    ans%=mod

print(ans%mod)

Solution (Python):
MOD=10**9+7
N=int(input())
A=list(map(int,input().split()))
res=1
cnt=[0]*3
for i in range(N):
    res=res*cnt.count(A[i])%MOD
    for j in range(3):
        if cnt[j]==A[i]:
            cnt[j]+=1
            break
print(res)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *



N = INT()
A = LIST()

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

print(ans)

Solution (Python):
import sys
from collections import defaultdict, deque, Counter
import math


from bisect import bisect_left, bisect_right





input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def era(n):
    ret = [1 for i in range(n + 2)]
    for i in range(2, int(math.sqrt(n) +3)):
        if ret[i] != 0:
            for j in range(2, n//i + 1):
                ret[i * j] = 0
    rret = []
    for i, r in enumerate(ret):
        if r == 1 and i != 0:
            rret.append(i)

    return rret


def houjyo(n, m, k, kaijyo):
    
    
    if k == n:
        return 1
    else:
        
        ret = nck(n,k,kaijyo) * npk(m-k, n-k, kaijyo) 
        
        return ret % MOD


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret


def solve():
    n = getN()
    nums = getList()

    ref = [0,0,0]
    ans = 1
    for num in nums:
        tmp = num
        ref.sort()
        if ref[0] == tmp:
            if ref[0] == ref[1]:
                if ref[0] == ref[2]:
                    ans *= 3
                else:
                    ans *= 2
            ref[0] += 1

        elif ref[1] == tmp:
            if ref[1] == ref[2]:
                ans *= 2

            ref[1] += 1
        elif ref[2] == tmp:
            ref[2] += 1
        else:
            print(0)
            return
        ans %= MOD
        

    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    
    solve()

Solution (Python):
N = int(input())
A = map(int, input().split())
B = [3 if i == 0 else 0 for i in range(N + 1)]
MOD = 1000000007
ans = 1
for a in A:
    ans = ans * B[a] % MOD
    if ans == 0:
        break
    else:
        B[a] -= 1
        B[a + 1] += 1
print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    A = in_nl()

    mod = 10**9 + 7
    num = [0] * 3
    ans = 1

    for i in range(N):
        min_j = 4
        count = 0
        for j in range(3):
            if num[j] == A[i]:
                count += 1
                min_j = min(min_j, j)
        if min_j == 4:
            ans = 0
            break
        num[min_j] += 1
        ans *= count
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()