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):
mod = 1000000007

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

C = [0,0,0]
ans = 1
i = 0
while i < N:
  a = A[i]
  cnt = sum([1 if C[j] == a else 0 for j in range(3)])
  ans = (ans*cnt)%mod
  if C[0] == a:
    C[0] += 1
  elif C[1] == a:
    C[1] += 1
  else:
    C[2] += 1
  i += 1
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")











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

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

ans=1
for i in A:
    ans *=DP[i]
    ans %=mod
    DP[i] -=1
    DP[i+1] +=1
print(ans)

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

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

Solution (Python):
import sys













import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n = ni()
    a = na()

    d = [0, 0, 0]

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys













import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n = ni()
    a = na()

    d = [0, 0, 0]

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def solve(N, A):
    ret = ModInt(1)
    count = [3 if not i else 0 for i in range(N + 1)]

    for a in A:
        ret *= count[a]
        if not ret:
            break
        count[a] -= 1
        count[a + 1] += 1

    return ret

if __name__ == "__main__":
    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()))












if a[0]!=0:
    print(0)
    sys.exit()
 
mod=10**9+7
acnt=dict()
acnt[a[0]]=1
acntkeymax=0
t=3
for i in range(1,n):

    if a[i] in acnt:
        acnt[a[i]]+=1
        if acnt[a[i]]>3:
            print(0)
            sys.exit()
    else:
        if acntkeymax+1==a[i]:
            acntkeymax=a[i]
            acnt[a[i]]=1
        else:
            print(0)
            sys.exit()

    if a[i]!=0:
        if acnt[a[i]-1]==1:
            if acnt[a[i]]!=1:
                print(0)
                sys.exit()
        elif acnt[a[i]-1]==2:
            if acnt[a[i]]==1:
                t=(t*2)%mod
            elif acnt[a[i]]!=2:
                print(0)
                sys.exit()
        elif acnt[a[i]-1]==3:
            if acnt[a[i]]==1:
                t=(t*3)%mod
            elif acnt[a[i]]==2:
                t=(t*2)%mod
            elif acnt[a[i]]!=3:
                print(0)
                sys.exit()
    else:
        if acnt[0]==2:
            t=(t*2)%mod
        elif acnt[0]!=3:
            print(0)
            sys.exit()


                
print(t)

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

mod = 10**9 + 7

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

print(ans % mod)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=list(map(int,input().split()))
    cunt=[0]*(n+1)
    cunt[0]=3
    ans=1
    mod=10**9+7
    for a in A:
        ans=ans*cunt[a]%mod
        if ans==0:break
        cunt[a+1]+=1
        cunt[a]-=1
    print(ans)
    

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    A=list(map(int,input().split()))
    rgb=[-1,-1,-1]
    ans=1
    mod=10**9+7
    for a in A:
        ans=ans*Counter(rgb)[a-1]%mod
        if ans==0:break
        rgb[rgb.index(a-1)]+=1
    print(ans)
    

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    A=list(map(int,input().split()))
    rgb=[-1,-1,-1]
    ans=1
    mod=10**9+7
    for a in A:
        ans=ans*Counter(rgb)[a-1]%mod
        if ans==0:break
        rgb[rgb.index(a-1)]+=1
    print(ans)
    

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()
L=[1,0,0]
ans=3
for i in range(1,N):
    a=A[i]
    count=0
    add=True
    for j,l in enumerate(L):
        if a==l:
            count+=1
            if add:
                L[j]+=1
                add=False

    ans*=count
    ans%=mod
print(ans)

Solution (Python):

"""
適当に色を割り振って良い。
[0,0,0]の状態から、その数字がいくつあるかを掛けていく
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1 = list(map(int,readline().split()))
mod = 10**9+7

RGB = [0,0,0]
ans = 1
for i in lst1:
    ans*= RGB.count(i)
    ans %= mod
    if not ans:
        print(ans)
        exit()
    for j in range(3):
        if RGB[j] == i:
            RGB[j] += 1
            break
print(ans)

Solution (Python):

def resolve():
    MOD = 1000000007
    N = int(input())
    A = list(map(int, input().split()))

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

    print(ans)
    
if __name__ == "__main__":
    resolve()

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
a = na()

x = 0
y = 0
z = 0

def count(m):
    cnt = 0
    cnt += x == m
    cnt += y == m
    cnt += z == m
    return cnt

ans = 1
for i in range(n):
    ans *= count(a[i])
    if x == a[i]:
        x += 1
    elif y == a[i]:
        y += 1
    elif z == a[i]:
        z += 1

print(ans % mod)

Solution (Python):



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

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


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

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

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

ans = 1
for i in range(1, N+1):
    plus_flg = True
    tmp = 0
    for j in range(3):
        xyz[i][j] = xyz[i-1][j]
        if xyz[i-1][j] == A[i-1]:
            tmp += 1
            if plus_flg:
                xyz[i][j] = xyz[i-1][j] + 1
                plus_flg = False
    ans *= tmp
    ans %= MOD

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

    for a in A:
        res = res * cnt[a] % mod
        cnt[a] -= 1
        cnt[a + 1] += 1

    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
l=[3]+[0]*(10**5)
m=10**9+7
x=1
for i in a:
  if l[i]:
    x=(x*l[i])%m
    l[i]-=1
    l[i+1]+=1
  else:
    x=0
    break
print(x)

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

res = 1
l = [0]*(n+1)
l[0] = 3
for a in list(map(int, input().split())):
    if l[a]<l[a+1]:
        print(0)
        exit()
    res = (res*(l[a] - l[a+1]))%mod
    l[a+1] += 1
print(res)

Solution (Python):
def main():
  n=int(input())
  a=list(map(int,input().split()))
  mod=pow(10,9)+7
  dp=[0,0,0] 
  ans=1
  for ai in a:
    if ai in dp:
      ans*=dp.count(ai)
      ans%=mod
      dp[dp.index(ai)]+=1
    else:
      print(0)
      exit()
  print(ans)
if __name__=='__main__':
  main()

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
ans = 1
cnt = [0] * N
for i, a in enumerate(A):
    cnt[a] += 1
    if a == 0:
        ans *= 4 - cnt[a]
    else:
        ans *= max(0, cnt[a-1]-cnt[a]+1)
    ans %= MOD

print(ans)

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

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

MOD = 10**9+7

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

    cnt = [0] * N
    ans = 1
    for a in A:
        if a == 0:
            cnt[0] += 1
            continue
        ans *= cnt[a - 1] - cnt[a]
        ans %= MOD
        cnt[a] += 1
        
    if cnt[0] == 1:
        ans *= 3
    elif cnt[0] <= 3:
        ans *= 6
    else:
        ans = 0
    
    ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

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

ans = 1
num_color = [-1, -1, -1]
for a in A:
  ans = (ans * num_color.count(a-1)) % MOD
  try:
    num_color[num_color.index(a-1)] = a
  except:
    print(0)
    quit()

print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
MOD = 1000000007
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = LI()

    
    color_number = [[0, 0, 0] for _ in range(N)]
    for i in range(N-1):
        if A[i] in color_number[i]:
            idx = color_number[i].index(A[i])
        else:
            idx = -1
        for j in range(3):
            if j==idx:
                color_number[i+1][j] = color_number[i][j] + 1
            else:
                color_number[i+1][j] = color_number[i][j]

    ans = 1
    for i in range(N):
        ans *= color_number[i].count(A[i])
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    resolve()

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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, 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
from fractions import gcd
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

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):
if __name__ == '__main__':
    n = int(input())
    a = list(map(lambda x: int(x) + 1, input().split()))
    counts = [0] * (n + 1)
    counts[0] = 3
    ans = 1
    for i in range(n):
        ans *= counts[a[i] - 1]
        ans %= (10 ** 9 + 7)
        counts[a[i] - 1] -= 1
        counts[a[i]] += 1
    print(ans)

Solution (Python):
if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    x, y, z = [0], [0], [0]
    for i in range(n):
        if a[i] == 0:
            if x[-1] == 0:
                x.append(1)
                y.append(y[-1])
                z.append(z[-1])
            elif y[-1] == 0:
                x.append(x[-1])
                y.append(1)
                z.append(z[-1])
            else:
                x.append(x[-1])
                y.append(y[-1])
                z.append(1)
        else:
            if x[-1] == a[i]:
                x.append(x[-1] + 1)
                y.append(y[-1])
                z.append(z[-1])
            elif y[-1] == a[i]:
                x.append(x[-1])
                y.append(y[-1] + 1)
                z.append(z[-1])
            else:
                x.append(x[-1])
                y.append(y[-1])
                z.append(z[-1] + 1)

    ans = 1
    for i in range(n):
        ans *= [x[i], y[i], z[i]].count(a[i])
        ans %= (10 ** 9 + 7)

    print(ans)

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

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

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

p =10**9+7

cnt= [0]*n
cnt[0]=1
ans = 3

if a[0]!=0:
    print(0)
    exit()

for i in range(1,n):
    if a[i]==0:
        ans *= (3-cnt[a[i]])
    else:
        ans *= (cnt[a[i]-1] - cnt[a[i]])
        if cnt[a[i]-1]==0:
            print(0)
            exit()

    ans%=p
    cnt[a[i]] += 1
    if cnt[a[i]]>3:
        print(0)
        exit()

print(ans%p)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
caps = [0, 0, 0]
ans = 1
for i in range(n):
    equal = []
    for j in range(3):
        if caps[j] == a[i]:
            equal.append(j)
    l = len(equal)
    if l == 0:
        ans = 0
        break
    ans = ans * l % mod
    caps[equal[0]] += 1
print(ans)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    ans = 1
    mod = 10 ** 9 + 7
    for i in range(n):
        A[i] += 1

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

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


resolve()

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

Solution (Python):
_, a = open(0)
mod = 10**9+7
c = 1
l = [3] + [0]*10**6

for a in a.split():
  a = int(a)
  c = c * l[a] % mod
  l[a] -= 1
  l[a+1] += 1
print(c)

Solution (Python):
import sys
import math  
import bisect  
import queue  


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


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

    MOD = 1000000007

    res = 1
    cnt = {'R': 0, 'G': 0, 'B': 0}
    for a in A:
        cv = 0
        cc = 'R'
        for c, v in cnt.items():
            if v == a:
                cv += 1
                cc = c
        res *= cv
        res %= MOD
        cnt[cc] += 1

    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
MOD=1000000007
hats=[0,0,0]
ans=1
for i in range(n):
    ai=a[i]
    ans=((ans%MOD)*hats.count(ai))%MOD
    if(ans==0):
        break
    hats[hats.index(ai)]+=1

print(ans%MOD)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = map(int, read().split())
ans = 1
mod = 10 ** 9 + 7
memo = [0, 0, 0]
for check in a:
    if check in memo:
        ans *= memo.count(check)
        ans %= mod
        memo[memo.index(check)] += 1
    else:
        print(0)
        exit()
print(ans)

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

colors = [0]*3
ans = 1
for i in range(n):
    c = colors.count(A[i])
    ans = ans*c % MOD
    if c == 0:
        break
    colors[colors.index(A[i])] += 1

print(ans % MOD)

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

colors = [0]*3
dp = [0]*n
for i in range(n):
    c = colors.count(A[i])
    dp[i] = c
    if c == 0:
        break
    colors[colors.index(A[i])] += 1

ans = 1
for x in dp:
    ans = ans*x % MOD
print(ans % MOD)

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)

MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    RGB = [1, 0, 0]
    ans = 1
    if A[0] !=0:
        print(0)
        return
    for i in range(1, N):
        a = A[i]
        if a == 0:
            if 0 in RGB:
                j = RGB.index(a)
                RGB[j] += 1
            else:
                print(0)
                return
        elif a not in RGB:
            print(0)
            return
        else:
            k = RGB.count(a)
            ans *= k
            ans %= MOD
            j = RGB.index(a)
            RGB[j] += 1
    z = RGB.count(0)
    if z == 0:
        ans *= 6
        ans %= MOD
    elif z == 1:
        ans *= 6
        ans %= MOD
    else:
        ans *= 3
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    ans = 1
    cnt = [0, 0, 0]
    for a in A:
        if a not in cnt:
            print(0)
            return
        i = cnt.index(a)
        c = cnt.count(a)
        cnt[i] += 1
        ans *= c
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

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

xyz = [[0,0,0]for _ in range(n)]
xyz[0] = [0,0,0]

mod = 10**9+7

for i in range(n-1):
    if li[i] not in xyz[i]:
        print(0)
        exit()
    ix = xyz[i].index(li[i])
    for j in range(3):
        if j == ix:
            xyz[i+1][j] = xyz[i][j] + 1
        else:
            xyz[i+1][j] = xyz[i][j]

point = 3

for i in range(1,n):
    point *= xyz[i].count(li[i])
    point %= mod
print(point)

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

N = int(input())
A = list(map(int, input().strip().split(" ")))
dp = {i: dict() for i in range(N)}
mod = 10 ** 9 + 7

def f(i, ma, mi):
    if i == N:
        return 1
    if (ma, mi) in dp[i]:
        return dp[i][(ma, mi)]
    if A[i] != ma and A[i] != mi and A[i] != i - ma - mi:
        dp[i][(ma, mi)] = 0
        return 0

    ans = 0
    
    if A[i] == ma:
        ans += f(i + 1, ma + 1, mi)
    if A[i] == mi:
        if ma > mi + 1:
            ans += f(i + 1, ma, mi + 1)
        else:
            ans += f(i + 1, mi + 1, ma)
    if A[i] == i - ma - mi:
        ans += f(i + 1, ma, mi)

    dp[i][(ma, mi)] = ans % mod
    return ans % mod

print(f(0, 0, 0) % mod)

Solution (Python):
M = 1000000007
N = int(input())
left = list(map(int, input().split()))


def solve():
    res = 1
    h = [0, 0, 0]
    for i in range(N):
        k = h.count(left[i])
        res = res * k % M
        for j in range(3):
            if h[j] == left[i]:
                h[j] += 1
                break
    return res


print(solve())

Solution (Python):
import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(sys.stdin.readline())
left = list(map(int, sys.stdin.read().split()))
counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    if sum(h) != N:
        return 0
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())

Solution (Python):
def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1
    d = [0] * (max(A) + 1)
    for a in A:
        if a == 0:
            ans *= 3 - d[a]
            ans %= MOD
            d[a] += 1
        else:
            ans *= d[a-1] - d[a]
            d[a] += 1
            ans %= MOD

    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
N, *A = map(int, open(0).read().split())

MOD = 10 ** 9 + 7
ctr = [0] * 3
ans = 1
for a in A:
    ans *= sum(a == v for v in ctr)
    for j in range(3):
        if ctr[j] == a:
            ctr[j] += 1
            break

print(ans % MOD)

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

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

ka = [[0]*3 for _ in range(n+1)]

for i in range(n):
    for j in range(3):
        ka[i+1][j] = ka[i][j]
        
    for j in range(3):
        if ka[i][j] == a[i]:
            ka[i+1][j] += 1
            break
    ka[i+1].sort(reverse = True)
    
ans = 1
for i in range(n):
    mlt = 0
    for j in range(3):
        if ka[i][j] == a[i]:
            mlt += 1
            
    ans = ans * mlt % MOD
        
print(ans)

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

DIV = 10**9 + 7













ABC = [0] * 3 

ans = 1
for i in range(N):
  num = A[i]
  first = True
  cnt = 0
  for j in range(len(ABC)):
    if ABC[j] == num:
      cnt += 1
      if first:
        ABC[j] += 1
        first = False
  ans = ((ans % DIV) * cnt)%DIV
  
print(ans)

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

print(ans%mod)

Solution (Python):
N=int(input())
A= list(map(int,input().split()))
B=[0,0,0]
C=1
for i in range(N):
 E=0
 F=0
 for j in range(3):
  if A[i]==B[j]:
   E+=1
   if E==1:
    B[j]+=1
    F=j
 C*=E
 C%=1000000007
print(C)

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

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
fac = [1 for _ in range(n+1)]
mod = 10 ** 9 + 7

ans = 1

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

print(ans)

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

RGB = [1,0,0]
M = 1000000007

c = 3

f = False
if A[0] != 0:
    f = True

for i in range(1,N):
    try:
        cnt = RGB.count(A[i])
        idx = RGB.index(A[i])
    except:
        f = True
        break
    c = (c * cnt)%M
    RGB[idx] += 1
    
if f:
    print(0)
else:
    print(c)

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 j in range(3):
        if a[i] == c[j]:
            if count == 0:
                c[j] += 1
            count += 1
    ans = ans * count % 1000000007
print(ans)

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 j in range(3):
        if a[i] == c[j]:
            if count == 0:
                c[j] += 1
            count += 1
    ans = ans * count % 1000000007
print(ans)

Solution (Python):
n = input()
A=[int(j) for j in input().split()]

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

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

B=[0]*(n+1)
B[0]=3
ans=1
for i in A:
    ans *=B[i]
    ans %=mod
    B[i] -=1
    B[i+1] +=1

print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)



def main():
    n = int(input())
    a = list(map(int,input().split()))
    cnt = [0] * (n + 1)
    cnt[0] = 3
    
    ans = 1
    for num in a:
        ans *= cnt[num]
        ans %= MOD
        cnt[num] -= 1
        cnt[num + 1] += 1
    
    print(ans)

if __name__ =='__main__':
    main()