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
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
mod = 1000000007
def main():
    N = I()
    L = LI()
    D = [0]*(N+2)
    D[0] = 3
    ans = 1
    
    for num in L:
        if D[num] == 0 or D[num+1] >= 3:
            print(0)
            sys.exit()
        temp = D[num] - D[num+1]
        D[num+1] += 1
        ans *= temp
        ans = ans % mod
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
mod = 1000000007

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

d = {-1:3}
ans = 1
for a in A:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
    if a-1 not in d:
        print(0)
        exit()
    ans = ans*d[a-1]%mod
    d[a-1] -= 1


print(ans)

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

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

from collections import defaultdict
dic = defaultdict(int)
dic[0] = 3
ans = 1

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

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

ans=1

d={}

ch=0

mod=10**9+7

for i in range(n):
  if a[i]==0:
    if 0 not in d:
      d[0]=1
      ans*=3
    else:
      if d[0]==1:
        d[0]=2
        ans*=2
      elif d[0]==2:
        d[0]=3
      else:
        ch+=1
        break
      
  else:
    if a[i] not in d:
      d[a[i]]=1
      if a[i]-1 not in d:
        ch+=1
        break
      else:
        ans*=d[a[i]-1]
    else:
      if d[a[i]]==1:
        d[a[i]]=2
        if a[i]-1 not in d:
          ch+=1
          break
        else:
          if d[a[i]-1]>=2:
            ans*=d[a[i]-1]-1
          else:
            ch+=1
            break
      elif d[a[i]]==2:
        d[a[i]]=3
        if a[i]-1 not in d:
          ch+=1
          break
        else:
          if d[a[i]-1]>=3:
            ans*=1
          else:
            ch+=1
            break
      else:
        ch+=1
        break
        
  ans=(ans%mod)
  
if ch==0:
  print(ans)
else:
  print(0)

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

ans = 1
l = [0] * N
for i in range(N):
  n = A[i]
  if 0 < n:
    ans *= l[n-1] - l[n]
  else:
    ans *= 3 - l[n]
  l[n] += 1
  ans %= 1000000007
print(ans)

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

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

R, B, G = 0, 0, 0
ans = 1

for a in A:
    if R == a:
        if B == a and G == a:
            ans *= 3
        elif B == a or G == a:
            ans *= 2
        else:
            ans *= 1
        R += 1
    elif B == a:
        if G == a:
            ans *= 2
        else:
            ans *= 1
        B += 1
    elif G == a:
        ans *= 1
        G += 1
    else:
        print(0)
        exit()
    
    ans %= 10**9+7

print(ans)

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

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

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

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

m = 10**9+7
r, b, g = 0, 0, 0
ans = 1

for aa in a:
    if aa == r == b == g:
        ans *= 3
    elif aa == r == b or aa == b == g or aa == g == r:
        ans *= 2
    elif aa != r and aa != b and aa != g:
        print(0)
        exit()
    ans %= m

    aa += 1
    if aa > r:
        r = aa
    elif aa > b:
        b = aa
    elif aa > g:
        g = aa

print(ans%m)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
G = [0]*3
ans = 1
for i in range(N):
    x = 0
    cnt = 0
    for j, g in enumerate(G):
        if g == A[i]:
            x = j if cnt == 0 else x
            cnt += 1
    
    G[x] += 1
    ans *= cnt
    ans = ans % mod

print(ans)

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

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

Solution (Python):
def main():
    n=int(input())
    lst=list(map(int,input().split()))
    mod=10**9+7
    sm=1
    color=[0,0,0]
    for x in lst:
        if x not in color : sm=0;break
        sm*=color.count(x)
        sm%=mod
        color[color.index(x)]+=1
    print(sm)

main()

Solution (Python):
N = int(input())
a = [int(x) for x in input().split()]
MOD = 10**9 + 7
ans = 1

lst = [0] * 3

for aa in a:
    cnt = 0
    j = -1
    for i, l in enumerate(lst):
        if l == aa:
            cnt += 1
            j = i
    if j == -1:
        ans = 0
        break
    ans *= cnt
    ans %= MOD
    lst[j] += 1

print(ans)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math








INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def run():
    N, *A = mapread()
    ans = 1
    current = [0,0,0]
    for a in A:
        transition = 0
        cache = None
        for i, c in enumerate(current):
            if c == a:
                transition += 1
                cache = i
        ans *= transition
        ans %= mod
        if cache == None:
            print(0)
            return
        current[cache] += 1
        
    print(ans)

if __name__ == "__main__":
    run()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math








INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def run():
    N, *A = mapread()
    ans = 1
    current = [0,0,0]
    for a in A:
        transition = 0
        cache = 0
        for i, c in enumerate(current):
            if c == a:
                transition += 1
                cache = i
        ans *= transition
        ans %= mod
        current[cache] += 1
        
    print(ans)

if __name__ == "__main__":
    run()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math








INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def run():
    N, *A = mapread()
    ans = 1
    current = [0,0,0]
    for a in A:
        transition = 0
        cache = 1
        for i, c in enumerate(current):
            if c == a:
                transition += 1
                cache = i
        ans *= transition
        ans %= mod
        current[cache] += 1
        
    print(ans)

if __name__ == "__main__":
    run()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math








INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def run():
    N, *A = mapread()

    dp = [defaultdict(lambda:0) for _ in range(N+1)]
    dp[0][(0,0,0)] = 1
    for i in range(N):
        a = A[i]
        k = i + 1
        for key in dp[k-1].keys():
            for ii, v in enumerate(key):
                if v == a:
                    tmp = list(key)
                    tmp[ii] += 1
                    dp[k][tuple(tmp)] += dp[k-1][key] % mod
    ans = 0
    for key in dp[N].keys():
        ans = (ans + dp[N][key]) % mod
    
    print(ans)


if __name__ == "__main__":
    run()

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))



N,A=ilint()
C=counter()
C.add(-1,3)
ans=1
for a in A:
    C.add(a)
    if a-1 not in C or C[a]>3:
        ans=0
        break
    ans*=C[a-1]-C[a]+1
    ans%=MOD
print(ans)

Solution (Python):
from collections import defaultdict
dic = defaultdict(int) 
N = int(input()); MOD = pow(10,9)+7
A = list(map(int,input().split()))


ans = 1
for x in A:
  if x == 0:
    if dic[x] == 0:
      ans *= 3%MOD
    elif dic[x] == 1:
      ans *= 2%MOD
    elif dic[x] == 2:
      ans *= 1%MOD
    else:
      print(0);exit()
  else:
    if dic[x-1]-dic[x] == 0:
      print(0);exit()
    elif dic[x-1]-dic[x] == 1:
      ans *= 1
    elif dic[x-1]-dic[x] == 2:
      ans *= 2%MOD
    elif dic[x-1]-dic[x] == 3:
      ans *= 3%MOD
  dic[x] += 1
print(ans%MOD)

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

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

print(ans)

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

MOD = 10**9+7

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

rgb = [0, 0, 0]

ans = 1
for i in range(n):
    ans *= rgb.count(a[i])
    ans %= MOD
    
    for j in range(3):
        if rgb[j] == a[i]:
            rgb[j] += 1
            break
print(ans)

Solution (Python):
import sys



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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    A = input_int_list()
    MOD = 10**9 + 7
    cnt = 1
    x, y, z = 0, 0, 0
    for a in A:
        tmp = 0
        is_used = False  
        if a == x:
            tmp += 1
            if not is_used:
                x += 1
                is_used = True
        if a == y:
            tmp += 1
            if not is_used:
                y += 1
                is_used = True
        if a == z:
            tmp += 1
            if not is_used:
                z += 1
                is_used = True
        cnt *= tmp
        cnt = cnt % MOD
    print(cnt)

    return


if __name__ == "__main__":
    main()

Solution (Python):

import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    targets = LI()

    colors = [0] * 3
    ans = 1

    for i in range(N):
        count = 0
        for k in range(3):
            if colors[k] == targets[i]:
                if count == 0:
                    colors[k] += 1
                count += 1
        ans *= count
        ans %= MOD

    print(ans)


main()

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

print(ans)

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

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

l=[0,0,0]

mod=10**9+7

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

print(ans)

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

l=[0,0,0]

mod=10**9+7

ans=1
for i in a:
  l_cnt=l.count(i)
  ans*=l_cnt
  ans%=mod
  for j in range(3):
    if l[j]==i:
      l[j]+=1
      break

print(ans)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
a=lnii()

l=[0,0,0]

mod=10**9+7

ans=1
for i in a:
  l_cnt=l.count(i)
  ans*=l_cnt
  ans%=mod
  for j in range(3):
    if l[j]==i:
      l[j]+=1
      break

print(ans)

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

A=list(map(int, input().split()))
p=10**9+7
if A[0]!=0:
    print(0)
    exit()

dp=[0]*N
dp[0]=3
counts=[0]*N 
counts[0]=1
for i in range(1,N):
    a=A[i]
    if a==0:
        dp[i]=(dp[i-1]*(3 - counts[a]))%p
    else:
        dp[i]=(dp[i-1]*(counts[a-1] - counts[a]))%p
    

    counts[a]+=1

print(dp[-1])

Solution (Python):
import sys

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

ans = 1
xyz = [0] * 3
for i in range(N):
    tmp = 0
    index = -1
    for j in range(3):
        if A[i] == xyz[j]:
            tmp += 1
            if index == -1:
                index = j

    xyz[index] += 1
    ans *= tmp
    ans %= mod

    
    

print(ans)

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

hat = [0,0,0]

mod = 10**9 + 7

ans=1

for i in range(n):
    tmp=0
    index=0
    for j,k in enumerate(hat):
        if k==a[i]:
            tmp+=1
            index=j

    ans = (ans*tmp)%mod

    hat[index]+=1

print(ans)

Solution (Python):
n, *a = map(int, open(0).read().split())
mita = [0] * -~n
mita[-1] = 3
mod = 10 ** 9 + 7
c = 1
for i in range(n):
    c = c * (mita[a[i] - 1] - mita[a[i]]) % mod
    mita[a[i]] += 1
print(c)

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 *= dp[x]
    dp[x] -= 1
    dp[x + 1] += 1
    ans %= MOD

print(ans)

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

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

Solution (Python):
N = int(input())
a = list(map(int,input().split()))
dp = [[-1,-1,-1,1] for _ in range(N+1)]
for i in range(N):
    check = dp[i][:3]
    pattern = check.count(a[i]-1)
    dp[i+1][3] *= dp[i][3]*pattern
    dp[i+1][3] = dp[i+1][3]%1000000007
    for k in range(3):
        dp[i+1][k]= dp[i][k]
    if dp[i][0]== a[i]-1:
        dp[i+1][0] = a[i]
    elif dp[i][1] ==a[i]-1:
        dp[i+1][1] = a[i]
    elif dp[i][2] ==a[i]-1:
        dp[i+1][2] = a[i]
print(dp[N][3])

Solution (Python):
N, *A = map(int, open(0).read().split())
MOD = 1_000_000_007
cnt = [0, 0, 0]
ans = 1
for a in A:
    possible = sum(c == a for c in cnt)
    ans *= possible
    ans %= MOD
    for i in range(3):
        if cnt[i] == a:
            cnt[i] += 1
            break
print(ans)

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

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

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

Solution (Python):
from collections import defaultdict

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

count = defaultdict(int)
count[0] = 3

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

Solution (Python):
import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n = read_int()
    a = read_int_list()
    ans = 1
    cnt = [3] + [0] * n
    for x in a:
        ans = ans * cnt[x] % MOD
        cnt[x] -= 1
        cnt[x + 1] += 1
    print(ans)

if __name__ == '__main__':
    Main()

Solution (Python):

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


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


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

    d = defaultdict(int)
    ans = 1
    d[-1] = 3
    for a in A:
        ans *= (d[a - 1] - d[a])
        ans %= 1000000007
        d[a] += 1
    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

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

mod = 10**9+7

A = [a+1 for a in A]
C = [0]*(n+1)
C[0] = 3
ans = 1
for a in A:
    if C[a-1] < C[a]:
        print(0)
        exit()
    else:
        ans *= C[a-1]-C[a]
        ans %= mod
        C[a] += 1
print(ans)

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

mod = 10**9+7

A = [a+1 for a in A]
C = [0]*(n+1)
C[0] = 3
ans = 1
for a in A:
    if C[a-1] < C[a]:
        print(0)
        exit()
    else:
        ans *= C[a-1]-C[a]
        ans %= mod
        C[a] += 1
print(ans)

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

ct = [0, 0, 0]
ans = 1
for a in A:
    cta = ct.count(a)
    if cta:
        ct[ct.index(a)] += 1
        ans = (ans * cta) % MOD
    else:
        print(0)
        exit()
print(ans)

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

counter = [0] * (n+1) ; counter[0] = 3
ans = 1
for i in range(n):
    ans *=  counter[a[i] - 1 +1] - counter[a[i] +1]
    ans = ans % M
    counter[a[i] +1] += 1
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a_=max(a)
con=[0]*(a_+1)
tou=[0]*(a_+1)
ans=[]
for i in range(len(a)):
    u=a[i]
    if u==0:
        con[0]+=1
        tou[0]+=1
        ans.append(4-con[0])

    else:
        con[u]+=1 
        tou[u]+=1  
        ans.append(tou[u-1]-con[u]+1)
c=1
for i in range(len(ans)):
    c*=ans[i]
    c=c%(10**9+7)
print(c%(10**9+7))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a_=max(a)
con=[0]*(a_+1)
tou=[0]*(a_+1)
ans=[]
for i in range(len(a)):
    u=a[i]
    if u==0:
        con[0]+=1
        tou[0]+=1
        ans.append(4-con[0])

    else:
        con[u]+=1 
        tou[u]+=1  
        ans.append(min(tou[u-1]-con[u]+1,4-con[u]))
c=1
for i in range(len(ans)):
    c*=ans[i]
    c=c%(10**9+7)
print(c%(10**9+7))

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

kMod = 10**9+7

mem = [0, 0, 0]
cnt = 1

for a in A:
   if a not in mem:
       cnt = 0
       break
   cnt *= mem.count(a)
   cnt %= kMod
   mem[mem.index(a)] = a+1
print(cnt)

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

dp=[1]
col=[]
for i in range(N):
    if A[i]==0:
        col.append(1)
        dp.append(dp[-1]*(4-len(col)))
    else:
        p=0
        for c in range(len(col)):
            if col[c]==A[i]:
                p+=1
                if p==1:
                    col[c]+=1
        dp.append(dp[-1]*p%mod)

print(dp[-1]%mod)

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

cnt=[0,0,0]
ans=1
mod=10**9+7

for aa in a:
    tmp=0
    for c in cnt:
        if aa==c:
            tmp+=1
    
    if tmp>0:
        for i in range(3):
            if cnt[i]==aa:
                cnt[i]+=1
                break
    
    ans*=tmp
    ans%=mod

print(ans)

Solution (Python):


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

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

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

col = [0, 0, 0]
ans = 1
for a in A:
    if a not in col:
        print(0)
        break
    ans = ans * col.count(a) % mod
    col[col.index(a)] += 1
else:
    print(ans)

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

cnt = [0]*n
ans = 1

for i in a:
    if i>0: ans *= max(0,cnt[i-1] - cnt[i])
    cnt[i] += 1
    if cnt[i]>3:ans = 0
    ans %= mod

ans *= 3 if cnt[0]==1 else 6

print(ans%mod)

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

mod = 10**9+7
ans = 1
hat = [0, 0, 0]

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

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

if a_ls[0] != 0 or (n != 1 and a_ls[1] == 2):
    print(0)
    sys.exit()

for i in range(1,n):
    n_same = a_ls[i]
    n_choices = 0
    choice_ind = -1
    for j,person in enumerate(hat_nperson):
        if person == n_same:
            n_choices += 1
            choice_ind = j
    if choice_ind == -1:
        print(0)
        sys.exit()
    hat_nperson[choice_ind] += 1
    ans *= n_choices
    ans %= mod
print(ans%mod)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

N = I()
A = LI()
mod = 10**9+7

ans = 1
x,y,z = -1,-1,-1
for i in range(N):
    a = A[i]
    k = [x,y,z].count(a-1)
    if k == 3:
        ans *= 3
        ans %= mod
        z += 1
    elif k == 2:
        ans *= 2
        ans %= mod
        if x == a-1:
            x = a
        elif y == a-1:
            y = a
        else:
            z = a
    elif k == 1:
        if x == a-1:
            x = a
        elif y == a-1:
            y = a
        else:
            z = a
    else:
        print(0)
        exit()

print(ans)

Solution (Python):
from collections import defaultdict

p = 10 ** 9 + 7
n = int(input())
a = [int(x) for x in input().split()]

num = defaultdict(int)
num[-1] = 3
col = [None] * n
for i in range(n):
    col[i] = num[a[i] - 1]
    num[a[i]] += 1
    num[a[i] - 1] -= 1

ans = 1
for i in range(n):
    ans = ans * col[i] % p

print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
N = int(input())
A = [int(i) for i in input().split()]
sums = [[0] * 3 for _ in range(N + 1)]

ans = 1
for i, a in enumerate(A):
    f = True
    count = 0
    for j in range(3):
        sums[i + 1][j] = sums[i][j]
        if sums[i][j] == a:
            count += 1
            if f:
                sums[i + 1][j] += 1
                f = False
    ans = ans * count % MOD

print(ans)

Solution (Python):


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

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

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

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(map(int, input().split()))
MOD = 1000000007

counts = [0, 0, 0]
result = 1
for i in range(n):
    a = A[i]
    
    cnt = counts.count(a)
    result *= cnt
    result %= MOD
    for j in range(len(counts)):
        if counts[j] == a:
            counts[j] += 1
            break

print(result)