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 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()

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

print(ans)

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

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

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


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

Solution (Python):
n = int(input())
a_list = list(map(int,input().split()))
a_dic = {}
for i in range(n):
  a_dic[i] = 3

ans = 1
for a in a_list:
  if a == 0:
    ans = ans * a_dic[a]
    a_dic[a] -= 1
  else:
    ans = ans * (a_dic[a] - a_dic[a-1])
    a_dic[a] -= 1
    
print(ans % (10**9 + 7))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
m = 1000000007
d = [0,0,0]
ans = 1
for i in range(n):
    if d[0] == d[1] == d[2] == a[i]:
        ans *= 3
        d[0] += 1
    elif (d[0] == d[1] or d[1] == d[2]) and a[i] == d[1]:
        ans *= 2
        d[1] += 1
    elif a[i] == d[0]:
        d[0] += 1
    elif a[i] == d[1]:
        d[1] += 1
    elif a[i] == d[2]:
        d[2] += 1
    
    else:
        ans = 0
        break
      
    ans %= m
    d = sorted(d,reverse=True)
print(ans)

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

status = [0, 0, 0]
mod = 1000000007

ans = status.count(a[0])
status[0] += 1

for i in range(1, n):
    ans *= status.count(a[i])
    ans %= mod

    for j in range(len(status)):
        if status[j] == a[i]:
            status[j] += 1
            break

print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
C = [0,0,0]
Ans = 1
MOD = 1000000007
for a in A:
    ask = C.count(a)
    if ask==0:
        Ans=0
        break
    ind = C.index(a)
    C[ind] += 1
    Ans = (Ans*ask)%MOD
print(Ans)

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

    print(ans)

    



if __name__ == "__main__":
    main()

Solution (Python):


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

def main():
    N=int(input())
    A=list(map(int,input().split()))
    cnt=[0]*N
    ans=1
    for i in range(N):
        if A[i]==0:
            ans*=3-cnt[0]
            ans%=MOD
            cnt[A[i]]+=1
        else:
            ans*=cnt[A[i]-1]-cnt[A[i]]
            ans%=MOD
            cnt[A[i]]+=1
    print(ans)
        
    
    
    
if __name__=="__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
c = [0,0,0]
count = 1
for i in range(n):
    match = (a[i]==c[0])+(a[i]==c[1])+(a[i]==c[2])
    if match==0:
        count = 0
        break
    elif match==1 or a[i]==0:
        c[c.index(a[i])] += 1
    else:
        c[c.index(a[i])] += 1
        count = (count*match)%(1e+9+7)
               
if count != 0:
    c = sorted(c,reverse=True)
    while 0 in c:
        c.pop()
    memory = set()
    kinds = 0
    for x in c:
        if not x in memory:
            kinds += 1
    for i in range(3,3-kinds,-1):
        count = (count*i)%(1e+9+7)

print(int(count))

Solution (Python):

import sys

MOD = 1000000007  


def solve(N: int, A: "List[int]"):
    from functools import reduce
    xyz_list = [[0]*3]
    for a in A:
        xyz_list.append(xyz_list[-1][:])
        for i, v in enumerate(xyz_list[-1]):
            if v == a:
                xyz_list[-1][i] += 1
                break
    T = [xyz.count(a) for xyz, a in zip(xyz_list, A)]
    return reduce(lambda a,b: a*b%MOD, T)


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)]  
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
n,*a=map(int,open(0).read().split())
mod=10**9+7
l=[0]*(n+1)
l[0]=3
ans=1
for ai in a:
  ans*=l[ai]
  ans%=mod
  l[ai]-=1
  l[ai+1]+=1
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




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

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

MAX = 2 * 10 ** 5 + 5
count = [0] * N
count[0] = 1
ans = 3
MOD = 10 ** 9 + 7
for a in A[1:]:
    if a == 0:
        ans *= 3 - count[0]
    else:
        ans *= count[a - 1] - count[a]
    ans %= MOD
    count[a] += 1

print(ans % MOD)

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

m = 1000000007

result = 1
t = [0, 0, 0]
for i in range(N):
    a = A[i]
    f = -1
    k = 0
    for j in range(3):
        if t[j] == a:
            k += 1
            if f == -1:
                t[j] += 1
                f = j
    result *= k
    result %= m
print(result)

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

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

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

MOD = 10**9 + 7

dp = [0] * (n + 1)
dp[0] = 3
ans = 1
for x in arr:
    ans = ans * dp[x] % MOD
    
    dp[x] -= 1
    
    dp[x + 1] += 1

print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  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 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 make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N = I()
A = IL()

dic = DD(int)
dic[-1] = 3
ans = 1
for a in A:
  ans *= dic[a-1]
  ans %= 10**9+7
  dic[a] += 1
  dic[a-1] -= 1
print(ans)

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

Solution (Python):
n = int(input())
dat = map(int, input().split())
dat = list(dat)
buf = [0] * 100100
buf[0] = 3
res = 1
M = (10**9 + 7)
for i in range(n):
    x = dat[i]
    res *= buf[x]
    res %= M
    buf[x] -= 1
    buf[x+1] += 1
print(res)

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

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):
n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7

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

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

Solution (Python):
import itertools

N = int(input())
Ali = list(map(int,input().split()))
C = [0,0,0]

for i in range(N):
  n = 0
  for j in range(3):
    if C[j] == Ali[i]:
      C[j] += 1
      break
  
Ali = Ali[::-1]
if C[0] == C[1] == C[2]:
  r = 1
elif C[0] == C[1] or C[1] == C[2] or C[2] == C[0]:
  r = 3
else:
  r = 6

  
for i in range(N):
  n = 0
  ta = 0 
  for j in range(3):
    if C[j]-1 == Ali[i]:
      n += 1
      ta = j
  r *= n
  C[ta] = Ali[i]
  
print(r%1000000007)

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

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N = NI()
    A = NLI()
    nowRGB = [0, 0, 0]
    ans = 1
    for a in A:
        ans *= nowRGB.count(a) % MOD
        for i in range(3):
            if nowRGB[i] == a:
                nowRGB[i] += 1
                break

    print(ans%MOD)



if __name__ == "__main__":
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    ans = 1
    C = [0, 0, 0]
    for a in A:
        try:
            ans = (ans * C.count(a)) % MOD
            C[C.index(a)] += 1
        except ValueError:
            print(0)
            return

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9+7
    
    check = [[] for _ in range(N)]
    for i in range(N):
        check[A[i]].append(i)
    
    
    ans = 1
    for i in range(len(check[0])):
        ans *= (3-i)

    for i in range(1,N):
        if len(check[i-1]) < len(check[i]):
            exit(print(0))
        
        for j in range(len(check[i])):
            d = bisect_right(check[i-1],check[i][j])
            if d < j:
                exit(print(0))
            ans *= d-j
            ans %= p
            
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
ans = 1
MOD = 1000000007
c = [0, 0, 0]
for a in A:
    cnt = c.count(a)
    if cnt == 0:
        print(0)
        exit()
    ans *= cnt
    ans %= MOD
    c[c.index(a)] += 1
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N = getN()
A = getList()

numlist = [0] * N
list_zero = 3
ans = 1

for i in range(N):
    if A[i] == 0:
        ans *= list_zero
        list_zero -= 1
        numlist[0] += 1
    else:
        ans *= numlist[A[i] - 1]
        numlist[A[i] - 1] -= 1
        numlist[A[i]] += 1
    ans %= mod
print(ans % mod)

Solution (Python):



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


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

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

print(ans)

Solution (Python):
import sys
l = [0] * 3
n = int(input())
a = [int(i) for i in input().split()]
m = 1000000007
ans = 1
for i in a:
    if(l.count(i) == 3):
        ans = ans * 3 % m
        l[0] += 1
    elif(l.count(i) == 2):
        ans = ans * 2 % m
        l = [i+1, i, sum(l)-2*i]
    elif(l.count(i) == 1):
        l[l.index(i)] += 1
    else:
        print(0)
        sys.exit()

print(ans)

Solution (Python):
import sys
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
mod = 10**9 + 7
color = A.count(0)
ans = 1
cnt = [0] * N
for a in A:
    if a > 0:
        ans *= (cnt[a - 1] - cnt[a])
    cnt[a] += 1
    ans %= mod
for i in range(cnt[0]):
    ans *= 3 - i
print(ans % mod)

Solution (Python):
import sys
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
mod = 10**9 + 7
ans = 1
cnt = [0] * N
for a in A:
    if a > 0:
        ans *= (cnt[a - 1] - cnt[a])
    cnt[a] += 1
    ans %= mod
for i in range(cnt[0]):
    ans *= 3 - i
print(ans % mod)

Solution (Python):
import sys
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
mod = 10**9 + 7
ans = 1
cnt = [0] * N
for a in A:
    if a > 0:
        ans *= (cnt[a - 1] - cnt[a])
    cnt[a] += 1
    ans %= mod
for i in range(cnt[0]):
    ans *= 3 - i
    ans %= mod
print(ans)

Solution (Python):
import sys
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
mod = 10**9 + 7
ans = 1
cnt = [0] * N
for a in A:
    if a > 0:
        ans *= (cnt[a - 1] - cnt[a])
    else:
        ans *= (3 - cnt[a])
    cnt[a] += 1
    ans %= mod
print(ans)

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

dp = [[0]*3 for _ in range(N+1)]
ans = 1
for i in range(N):
    a = As[i]
    dplis = dp[i]
    cnt = 0
    dp[i+1] = dplis[:]
    for j, d in enumerate(dplis):
        if a==d:
            cnt += 1
            if cnt==1:
                dp[i+1][j] = a+1
    if cnt==0:
        print(0)
        break
    ans = ans*cnt%mod
else:
    print(ans%mod)

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

Solution (Python):
def f():
    n=int(input())
    l=[0,0,0]
    ans=1
    mod=10**9+7
    for i in list(map(int,input().split())):
        if i not in l:print(0);exit()
        ans=ans*l.count(i)%mod
        l[l.index(i)]+=1
    print(ans)
if __name__ == "__main__":f()

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


R=[0]
G=[0]
B=[0]


ans=1
for i in range(N):
    tmp=0
    if A[i]==R[-1]:
        tmp+=1
    if A[i]==G[-1]:
        tmp+=1
    if A[i]==B[-1]:
        tmp+=1
    ans = (ans*tmp)%p

    if A[i]==R[-1]:
        R.append(R[-1]+1)
        G.append(G[-1])
        B.append(B[-1])
    elif A[i]==G[-1]:
        R.append(R[-1])
        G.append(G[-1]+1)
        B.append(B[-1])
    else:
        R.append(R[-1])
        G.append(G[-1])
        B.append(B[-1]+1)
    



print(ans)

Solution (Python):
def main():
    mod = 1000000007
    n = int(input())
    cnt = [0] * (n + 2)
    cnt[0] = 3
    res = 1
    for x in input().split():
        v = int(x)
        res *= cnt[v] - cnt[v + 1]
        res %= mod
        cnt[v + 1] += 1
    print(res)

main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
Ans = [0] * (N+1)
mod = 1000000007
Ans[0] = 3
ans = 1
for a in A:
    a += 1
    ans *= Ans[a-1]
    ans %= mod
    Ans[a-1] -= 1
    Ans[a] += 1

print(ans % mod)

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

mod = 10**9 + 7
ans = 1
cnt = [0] * 3
for i in range(n):
    t = 0
    first = True
    for j in range(3):
        if cnt[j] == a[i]:
            t += 1
            if first:
                first = False
                cnt[j] += 1
    ans = (ans * t) % mod
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7
r = 0
b = 0
g = 0
ans = 1
for i in range(n):
    p = 0
    if a[i] == r:
        p += 1
        r += 1
    if a[i] == b:
        p += 1
        if p == 1:
            b += 1
    if a[i] == g:
        p += 1
        if p == 1:
            g += 1
    ans *= p
    ans %= mod
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())
A = list(map(int, input().split(' ')))
mod = 10 ** 9 + 7
c = [0, 0, 0]
ans = 1
for i in A:
    ans *= c.count(i)
    if i == c[0]:
        c[0] += 1
    elif i == c[1]:
        c[1] += 1
    else:
        c[2] += 1
    ans %= mod
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
current = [-1]*3
MOD = 1000000007
res = 1
for c in a:
    cnt = 0
    for can in current:
        if can == c-1:
            cnt += 1
    for i, v in enumerate(current):
        if v == c-1:
            current[i] = c
            break

    res *= cnt
    res %= MOD

res %= MOD
print(res)

Solution (Python):
import sys

import math





input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=1
d={x:0 for x in range(n)}
for i in range(n):
    if a[i]==0:
        d[0]+=1
    else:
        m=a[i]
        ans=(ans*(d[m-1]-d[m]))%mod
        if ans<=0:
          print(0)
          exit()
        d[m]+=1
    if d[a[i]]>3:
      print(0)
      exit()
if d[0]==1:
  print(ans*3%mod)
elif d[0]==2:
  print(ans*6%mod)
elif d[0]==3:
  print(ans*6%mod)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if a[0]!=0:
    print(0)
    exit()
r=1
b=0
g=0
pos=3
for i in range(1,n):
    pre=0
    de=0
    if a[i]==r:
        pre += 1
        r += 1
        de=1
    if a[i]==b:
        pre += 1
        if de==0:
            b += 1
            de=1
    if a[i]==g:
        pre += 1
        if de==0:
            g += 1
    
    pos *= pre
print(pos%(10**9+7))

Solution (Python):
def col_count(A,N,M):
    col = [[0,0,0] for _ in range(N+1)]
    for i in range(N):
        for j in range(3):
            col[i+1][j] = col[i][j]
        for j in range(3):
            if col[i][j] == A[i]:
                col[i+1][j] += 1
                break

    output = 1
    for i in range(N):
        cnt = 0
        for j in range(3):
            if col[i][j] == A[i]:
                cnt += 1

        output *= cnt
        output %= M
    return output

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

    print(col_count(A,N,M))

if __name__ == "__main__":
    main()

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

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, A = Z(), ZZ()
    cnt = [0] * (N)
    ng, output = 0, 1

    for a in A:
        if a == 0:
            ng += 1
            cnt[a] += 1
            continue
        cnt[a] += 1
        output *= cnt[a-1]
        output %= MOD
        cnt[a-1] -= 1
    ng = 6 if 2 <= ng <= 3 else 3 if ng == 1 else 0
    output *= ng
    output %= MOD
    print(output)

    return

if __name__ == '__main__':
    main()

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

h = [0 for _i in range(n)]+[3]
result = 1
mod = 10**9 +7
for i in a:
    result = (result*(h[i-1]-h[i]))%mod
    h[i] += 1
print(result)

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

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

Solution (Python):
n=int(input())
mod=1000000007
l=list(map(int,input().split()))
me=[3]+[0]*2*n
ans=1
for x in l:
  ans=ans*me[x]%mod
  me[x]-=1
  me[x+1]+=1
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
l=[[] for _ in range(3)]
ans=1
p=10**9+7
flag=1
for i in range(N):
    cnt=0
    piv=A[i]
    ind=[]
    for j in range(3):
        if len(l[j])==piv:
            cnt=cnt+1
            ind.append(j)
    if len(ind)==0:
        flag=0
        break
    l[ind[0]].append(piv)
    ans=(ans*cnt)%p
    
    
if flag==1:
    print(ans%p)
else:
    print(flag)

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





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()


	ans=1
	mod=10**9+7
	li=[3]+[0]*(n+1)

	for i in A:
		ans*=li[i]-li[i+1]
		ans%=mod
		li[i+1]+=1

	print(ans)


if __name__ == "__main__":
	main()

Solution (Python):
n = int(input())
A=[int(i) for i in input().split()]
MOD = 1000000007
ans = 1
cnt = [0]*(n+1)
cnt[0]=3

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

Solution (Python):
def main():
    import sys

    MOD = 1000000007
    N, *A = map(int, sys.stdin.buffer.read().split())
    C = [0] * (N + 1)
    C[0] = 3
    ans = 1
    for a in A:
        ans = ans * C[a]
        C[a] -= 1
        C[a + 1] += 1

    print(ans % MOD)
    return


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys

    MOD = 1000000007
    N, *A = map(int, sys.stdin.buffer.read().split())
    C = [0] * (N + 1)
    C[0] = 3
    ans = 1
    for a in A:
        ans = ans * C[a] % MOD
        C[a] -= 1
        C[a + 1] += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys

    MOD = 1000000007
    N, *A = map(int, sys.stdin.buffer.read().split())
    C = [0] * (N + 1)
    C[0] = 3
    ans = 1
    for a in A:
        ans = ans * C[a] % MOD
        C[a] -= 1
        C[a + 1] += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 1000000007
    N, *A = map(int, read().split())
    C = [0] * (N + 1)
    C[0] = 3
    ans = 1
    for a in A:
        ans = ans * C[a] % MOD
        C[a] -= 1
        C[a + 1] += 1

    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 1000000007
    N, *A = map(int, read().split())
    C = [0] * (N + 1)
    C[0] = 3
    ans = 1
    for a in A:
        ans = ans * C[a] % MOD
        if ans == 0:
            print(0)
            return
        C[a] -= 1
        C[a + 1] += 1

    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 1000000007
    N, *A = map(int, read().split())
    seq = [-1] * 3
    ans = 1
    try:
        for a in A:
            ans = ans * seq.count(a - 1) % MOD
            seq[seq.index(a - 1)] = a
        print(ans)
    except:
        print(0)
        
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 1000000007
    N, *A = map(int, read().split())
    seq = [-1] * 3
    ans = 1
    try:
        for a in A:
            ans = ans * seq.count(a - 1) % MOD
            seq[seq.index(a - 1)] = a
        print(ans)
    except:
        print(0)
        
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
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 i in range(N):
        a = A[i]
        count = 0
        if R==a:
            R+=1
            count+=1
            if G==a:
                count+=1
            if B==a:
                count+=1
        else:
            if G==a:
                G+=1
                count+=1
                if B==a:
                    count+=1
            else:
                if B==a:
                    B+=1
                    count+=1
                else:
                    print(0)
                    exit()
        ans*=count
        ans%=MOD
    print(ans)


if __name__ == '__main__':
    main()

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