CodeEff/ECCO huggingface dataset:
# Original solution
(n, m, l) = [int(i) for i in input().split()]
A = []
for nc in range(n):
    A.append([int(i) for i in input().split()])
B = []
for mc in range(m):
    B.append([int(i) for i in input().split()])

product = [[0 for d in range(l)] for dd in range(n)]

for nc in range(n):
    for lc in range(l):
        for mc in range(m):
            product[nc][lc] += A[nc][mc] * B[mc][lc]

for r in product:
    print((' '.join([str(d) for d in r])))

# Optimized solution
n, m, l = (int(i) for i in input().split())
A = []
B = []
#C = [[0] * n] * l
C = [[0 for i in range(l)] for j in range(n)]

#??\?????????????????????????´?
for i in range(n):
    #swap_list = input().split()
    #A.append(swap_list)
    A.append([int(i) for i in input().split()])
for i in range(m):
    #swap_list = input().split()
    #B.append(swap_list)
    B.append([int(i) for i in input().split()])
#????????????????¨????
for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k] * B[k][j]
#?????????????????????
#for i in range(n):
#    for j in range(l):
#        print("{0}".format(C[i][j]), end="\b")
#    print("")
#for i in range(n):
#    print(" ".join(map(str, C[i][:])))
for r in C:
    print((" ".join([str(d) for d in r])))
# Original solution
def main():
    n, m, l = tuple(map(int, input().split()))
    matA = [[0 for j in range(m)] for i in range(n)]
    matB = [[0 for k in range(l)] for j in range(m)]
    matC = [[0 for k in range(l)] for i in range(n)]

    for i in range(n):
        tmp = list(map(int, input().split()))
        for j in range(m):
            matA[i][j] = tmp[j]

    for j in range(m):
        tmp = list(map(int, input().split()))
        for k in range(l):
            matB[j][k] = tmp[k]


    for i in range(n):
        for k in range(l):
            for j in range(m):
                matC[i][k] += matA[i][j] * matB[j][k]

    for i in range(n):
        for k in range(l):
            if k == l-1:
                print(matC[i][k])
            else:
                print(matC[i][k], end=' ')

if __name__ == '__main__':
    main()


# Optimized solution
n, m, l = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
B = [list(map(int, input().split())) for _ in range(m)]
[print(*x) for x in [[sum(j*k for j,k in zip(x,y)) for y in zip(*B)] for x in A]]
# Original solution
import copy
a = [[0 for i in range(100)] for j in range(100)]
b = copy.deepcopy(a)
n, m, l = map(int, input().split())
for i in range(n):
    a[i][:m] = map(int, input().split())
for i in range(m):
    b[i][:l] = map(int, input().split())
for i in range(n):
    for j in range(l):
        c = 0
        for k in range(m):
            c += a[i][k] * b[k][j]
        print(c, end='')
        if j < l - 1:
            print(' ', end='')
        else:
            print()


# Optimized solution
a = [[0 for i in range(100)] for j in range(100)]
b = [[0 for i in range(100)] for j in range(100)]
n, m, l = map(int, input().split())
for i in range(n):
    a[i][:m] = map(int, input().split())
for i in range(m):
    b[i][:l] = map(int, input().split())
for i in range(n):
    for j in range(l):
        c = 0
        for k in range(m):
            c += a[i][k] * b[k][j]
        print(c, end='')
        if j < l - 1:
            print(' ', end='')
        else:
            print()
# Original solution
import sys

n, m, l = [ int( val ) for val in sys.stdin.readline().split( " " ) ]

matrixA = [ [ int( val ) for val in sys.stdin.readline().split( " " ) ] for row in range( n ) ]
matrixB = [ [ int( val ) for val in sys.stdin.readline().split( " " ) ] for row in range( m ) ]	
matrixC = [ [ 0 for row in range( l ) ] for row in range( n ) ]

output = []
for i in range( n ):
	for j in range( l ):
		for k in range( m ):
			matrixC[i][j] += ( matrixA[i][k] * matrixB[k][j] )
		output.append( "{:d}".format( matrixC[i][j] ) )
		output.append( " " )
	output.pop()
	output.append( "\n" )

output.pop()
print(( "".join( output ) ))

# Optimized solution
import sys

n, m, l = [ int( val ) for val in sys.stdin.readline().split( " " ) ]

matrixA = [ [ int( val ) for val in sys.stdin.readline().split( " " ) ] for row in range( n ) ]
matrixB = [ [ int( val ) for val in sys.stdin.readline().split( " " ) ] for row in range( m ) ]	
c = 0

output = []
for i in range( n ):
	for j in range( l ):
		c = 0
		for k in range( m ):
			c += ( matrixA[i][k] * matrixB[k][j] )
		output.append( "{:d}".format( c ) )
		output.append( " " )
	output.pop()
	output.append( "\n" )

output.pop()
print(( "".join( output ) ))
# Original solution
import sys

n, m, l = [ int( val ) for val in sys.stdin.readline().split( " " ) ]

matrixA = [ [ int( val ) for val in sys.stdin.readline().split( " " ) ] for row in range( n ) ]
matrixB = [ [ int( val ) for val in sys.stdin.readline().split( " " ) ] for row in range( m ) ]	
c = 0

output = []
for i in range( n ):
	for j in range( l ):
		c = 0
		for k in range( m ):
			c += ( matrixA[i][k] * matrixB[k][j] )
		output.append( "{:d}".format( c ) )
		output.append( " " )
	output.pop()
	output.append( "\n" )

output.pop()
print(( "".join( output ) ))

# Optimized solution
import sys

n, m, l = [ int( val ) for val in sys.stdin.readline().split( " " ) ]

matrixA = [ [ int( val ) for val in sys.stdin.readline().split( " " ) ] for row in range( n ) ]
matrixB = [ [ int( val ) for val in sys.stdin.readline().split( " " ) ] for row in range( m ) ]	
matrixC = [ [ sum( matrixA[i][k] * matrixB[k][j]  for k in range( m ) ) for j in range( l ) ] for i in range( n )  ]

for i in range( n ):
	print(( " ".join( map( str, matrixC[i] ) ) ))
# Original solution
n, m, l = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [list(map(int, input().split())) for _ in range(m)]
ans = [[0 for _ in range(l)] for _ in range(n)]
for i in range(n) :
    for j in range(l) :
        for k in range(m) :
            ans[i][j] += a[i][k] * b[k][j]
    print(*ans[i], sep = ' ')


# Optimized solution
n, m, l = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [list(map(int, input().split())) for _ in range(m)]
[print(*x) for x in [[sum(j*k for j,k in zip(x,y)) for y in zip(*b)] for x in a]]
# Original solution
n, m, l = map(int, input().split())
A = []
B = []
for _ in range(n):
    A.append(list(map(int, input().split())))
for _ in range(m):
    B.append(list(map(int, input().split())))

for i in range(n):
    for j in range(l):
        s = 0
        for k in range(m):
            s += A[i][k] * B[k][j]
        print(s, end='')
        if j != l-1:
            print(' ', end='')
    print()


# Optimized solution
n, m, l = list(map(int, input().split()))

A = []
for i in range(n):
    row = list(map(int, input().split()))
    A.append(row)

B = []
for i in range(m):
    row = list(map(int, input().split()))
    B.append(row)

C = []
for i in range(n):
    row = []
    for j in range(l):
        sum = 0
        for k in range(m):
            sum += A[i][k] * B[k][j]
        row.append(sum)
    C.append(row)

for i in range(n):
    print((' '.join(map(str, C[i]))))
# Original solution
n, m, l = map(int, input().split())
A = [[int(n) for n in input().split()] for i in range(n)]
B = [[int(n) for n in input().split()] for i in range(m)]
C = [[0 for i in range(l)] for i in range(n)]
for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k] * B[k][j]
for i in range(n):
    for j in range(l):
        if j == l - 1:
            print(C[i][j])
        else:
            print(C[i][j], end = " ")


# Optimized solution
n, m, l = map(int, input().split())
a = [[int(num) for num in input().split()] for i in range(n)]
b = [[int(num) for num in input().split()] for i in range(m)]
c = [[0 for i in range(l)] for j in range(n)]
for i in range(n):
    for j in range(l):
        for k in range(m):
            c[i][j] += a[i][k] * b[k][j]
for i in range(n):
    for j in range(l):
        if j == l - 1:
            print(c[i][j])
        else:
            print(c[i][j], end=" ")
# Original solution
if __name__ == '__main__':
	n,m,l=list(map(int,input().split()))
	a=[list(map(int,input().split())) for _ in [0]*n]
	b=list(zip(*[list(map(int,input().split())) for _ in [0]*m]))
	sums=[i[k]*j[k] for i in a for j in b for k in range(m)]
	c=[sum(sums[i:i+m]) for i in [j for j in range(len(sums)) if j%m==0]]
	for i in range(len(c)):
		if (i+1)%l==0: print(c[i])
		else: print(c[i], end=' ')

# Optimized solution
if __name__ == '__main__':
	n,m,l=list(map(int,input().split()))
	a=[list(map(int,input().split())) for _ in [0]*n]
	b=list(zip(*[list(map(int,input().split())) for _ in [0]*m]))
	sums=[i[k]*j[k] for i in a for j in b for k in range(m)]
	c=[sum(sums[i:i+m]) for i in [j for j in range(len(sums)) if j%m==0]]
	c=[c[i:i+l] for i in range(len(c)) if i%l==0]
	for i in c:
		print(" ".join(map(str, i)))
# Original solution
import sys
def cmb(n,r,mod):
  if r<0 or r>n:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod

n=int(eval(input()))
a=list(map(int,input().split()))
mod=10**9+7
g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n*2):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

ct=[0,0,0]
ans=1
for i in range(n):
  f=0
  ct2=0
  for j in range(3):
    if a[i]==ct[j]:
      if ct2==0:
        ct[j]+=1
      ct2+=1
  ans*=ct2
print((ans%mod))

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
mod=10**9+7

ct=[0,0,0]
ans=1
for i in range(n):
  f=0
  ct2=0
  for j in range(3):
    if a[i]==ct[j]:
      if ct2==0:
        ct[j]+=1
      ct2+=1
  ans*=ct2
  ans%=mod
print((ans%mod))
# Original solution
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    if A[0] != 0:
        print((0))
        return 

    ## 一番多い色の帽子の数
    color = [1,0,0]
    answer = 3

    for i in range(1,N):
        if A[i] not in color:
            print((0))
            return 
        
        count = color.count(A[i])
        answer *= count

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

    print((answer%MOD))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def INT(): return int(eval(input()))
def MAP(): return list(map(int,input().split()))
def LI(): return list(map(int,input().split()))

def main():
    N = INT()
    A = LI()
    RGB = [0,0,0]
    answer = 1
    MOD = 10**9+7

    for i in range(N):
        if RGB.count(A[i]) == 0:
            print((0))
            return

        answer *= RGB.count(A[i])
        answer %= MOD
        for j in range(3):
            if RGB[j] == A[i]:
                RGB[j] += 1
                break

    print(answer)
    return

if __name__ == '__main__':
    main()
# Original solution
from collections import defaultdict
N = int(eval(input()))

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

ans = 1
d = defaultdict(int)

for i,n in enumerate(A):
    if n == 0:
        ans *= (3-d[n])
        d[n] += 1
    else:
        ans *= (d[n-1] - d[n])
        d[n] += 1

print((ans % (10**9+7)))

# Optimized solution



N = int(eval(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)
# Original solution
# coding: utf-8
import sys
#from operator import itemgetter
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
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

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

def mapline(t = int):
    return list(map(t, sysread().split()))
def mapread(t = int):
    return list(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 list(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 list(dp[N].keys()):
        ans = (ans + dp[N][key]) % mod
    #print(dp)
    print(ans)


if __name__ == "__main__":
    run()


# Optimized solution
# coding: utf-8
import sys
#from operator import itemgetter
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
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

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

def mapline(t = int):
    return list(map(t, sysread().split()))
def mapread(t = int):
    return list(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(current)
    print(ans)

if __name__ == "__main__":
    run()
# Original solution
import sys
input = sys.stdin.readline

N = int(eval(input()))
A = list(map(int, input().split()))
cnt = [0]*N
p = 0
ans = 1
MOD = 10**9+7

for Ai in A:
    if Ai==0:
        cnt[Ai] += 1
        p += 1
    else:
        ans *= cnt[Ai-1]
        ans %= MOD
        cnt[Ai-1] -= 1
        cnt[Ai] += 1

if p==1:
    ans *= 3
elif p==2:
    ans *= 6
elif p==3:
    ans *= 6
else:
    ans = 0

print((ans%MOD))

# Optimized solution
import sys
input = sys.stdin.readline

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

for Ai in A:
    cnt = 0
    
    if r==Ai:
        cnt += 1
    
    if g==Ai:
        cnt += 1
    
    if b==Ai:
        cnt += 1
        
    ans *= cnt
    ans %= MOD
    
    if r==Ai:
        r += 1
    elif g==Ai:
        g += 1
    else:
        b += 1
    
print(ans)
# Original solution
N, *A = list(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))


# Optimized solution

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

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

    if ans == 0:
        break

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

print(ans)
# Original solution
import sys
input = sys.stdin.readline


def main():
    mod = 1000000007
    N = int(eval(input()))
    A = list(map(int, input().split()))
    cnt = [[0, 0, 0] for i in range(N+1)]
    ans = 1
    for i in range(N):
        a = A[i]
        ans = ans * cnt[i].count(a) % mod
        for j in range(3):
            cnt[i+1][j] = cnt[i][j]
        for j in range(3):
            if cnt[i][j] == a:
                cnt[i+1][j] = a+1
                break
    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
import sys
input = sys.stdin.readline


def main():
    mod = 1000000007
    N = int(eval(input()))
    A = list(map(int, input().split()))
    cnt = [0, 0, 0]
    ans = 1
    for a in A:
        ans = ans * cnt.count(a) % mod
        for j in range(3):
            if cnt[j] == a:
                cnt[j] = a+1
                break
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
n=int(eval(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)

# Optimized solution
n=int(eval(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)
# Original solution
#!/usr/bin/env python3
#三井住友信託銀行プログラミングコンテスト2019 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
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()
cnt = [0]*n
ans = 1
tmp = 3
for i in range(n):
    if a[i] == 0:
        ans *= tmp
        ans %= mod
        tmp -= 1
    else:
        ans *= cnt[a[i]-1]
        ans %= mod
        cnt[a[i]-1] -= 1
    cnt[a[i]] += 1
print(ans)

# Optimized solution
#!/usr/bin/env python3

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)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
MOD = 10**9+7
ans = 1
s = [0] * 3

for i in range(n):
    ans *= len([0 for x in s if x == a[i]])
    if ans == 0: break
    ans %= MOD
    for j in range(3):
        if s[j] == a[i]:
            s[j] += 1
            break

print((ans % MOD))


# Optimized solution
MOD = 10**9+7
n = int(eval(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)
# Original solution
def main():
    import sys
    N=int(eval(input()))
    MOD=1000000007
    
    a=list(map(int,input().split()))
    c=[0,0,0]
    ans=1
    for i in range(N):

        if a[i]!=c[0] and a[i]!=c[1] and a[i]!=c[2]:
            print((0))
            sys.exit()

        if c[1]==c[0] and c[2]==c[0]:
            ans=(ans*3)%MOD
            c[0]+=1

        elif c[0]==c[1]:
            if c[0]==a[i]:
                c[0]+=1
                ans=(ans*2)%MOD
            else:
                c[2]+=1

        elif c[0]>c[1] and c[1]==c[2]:
            if c[0]==a[i]:
                c[0]+=1
            else:
                ans=(ans*2)%MOD
                c[1]+=1
            
        else:
            if c[0]==a[i]: c[0]+=1
            if c[1]==a[i]: c[1]+=1
            if c[2]==a[i]: c[2]+=1
        
        c.sort(reverse=True)
    print(ans)


 
if __name__ == '__main__':
    main()

# Optimized solution
def main():
    import sys
    N=int(eval(input()))
    MOD=1000000007
    
    a=list(map(int,input().split()))
    c=[3]+[0]*N
    ans=1
    for i in range(N):
        p=a[i]
        ans=ans*c[p]%MOD
        c[p]-=1
        c[p+1]+=1

    print(ans)


 
if __name__ == '__main__':
    main()
# Original solution
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

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

def f(i, ma, mi):
    if i == N:
        return 1
    if (i, ma, mi) in dp:
        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
    # iがr, b, gを被って矛盾がないかを見ていく
    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 dp[(i, ma, mi)]

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

# Optimized solution
import sys
sys.setrecursionlimit(10 ** 6)

N = int(eval(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
    # iがr, b, gを被って矛盾がないかを見ていく
    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))
# Original solution
n=int(eval(input()))
l=list(map(int,input().split()))
mod=10**9+7
ans=1
rgb=[0]*3
for i in range(n):
    f=0
    for j in range(3):
        if l[i]==rgb[j]:
            if f==0:
                rgb[j]+=1
            f+=1
    ans*=f
    ans%=mod
print(ans)

# Optimized solution
mod=10**9+7
n=int(eval(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)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
d=[-1,-1,-1]
x=1
for i in a:
  b=0
  f=True
  for j in range(3):
    if d[j]==i-1:
      b+=1
      if f:
        f=False
        d[j]=i
  x*=b
  x%=10**9+7
print(x)

# Optimized solution
n=int(eval(input()))
d=[-1,-1,-1]
x=1
for i in list(map(int,input().split())):
  x*=d.count(i-1)
  x%=10**9+7
  if i-1 in d:d[d.index(i-1)]+=1
print(x)
# Original solution
def main():
  from collections import defaultdict
  N = int(eval(input()))
  A = list(map(int,input().split()))
  MOD = 1000000007
  c = defaultdict(int)
  c[0] = 3
  ans = 1
  for i in range(N):
    if not c[A[i]]:
      print((0))
      exit()
    ans *= c[A[i]]
    ans %= MOD
    c[A[i]] -= 1
    c[A[i]+1] += 1
  print(ans)
main()  
           

# Optimized solution
def main():
  N = int(eval(input()))
  A = list(map(int,input().split()))
  MOD = 1000000007
  c = [0] * (N+1)
  c[0] = 3
  ans = 1
  for i in range(N):
    if not c[A[i]]:
      print((0))
      exit()
    ans *= c[A[i]]
    ans %= MOD
    c[A[i]] -= 1
    c[A[i]+1] += 1
  print(ans)
main()