CodeEff/ECCO huggingface dataset:
# Original solution
from collections import Counter

MOD = 10**9 + 7

N = int(eval(input()))
As = list(map(int, input().split()))

ptns = Counter([(0, 0, 0)])
#print('ptns:', ptns)
for A in As:
    ptn2s = Counter()
    for ptn, num in list(ptns.items()):
        for i in range(3):
            if ptn[i] == A:
                ptn2 = list(ptn)
                ptn2[i] += 1
                ptn2s[tuple(ptn2)] += num
                ptn2s[tuple(ptn2)] %= MOD
    ptns = ptn2s

#print(ptns)
print((sum(ptns.values()) % MOD))


# Optimized solution
MOD = 10**9 + 7

N = int(eval(input()))
As = list(map(int, input().split()))

ans = 1
numRGBs = [0] * 3
for A in As:
    num = 0
    for i in range(3):
        if numRGBs[i] == A:
            num += 1
            if num == 1:
                numRGBs[i] += 1
    ans *= num
    ans %= MOD

print(ans)
# Original solution

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
AA = inpl()

cnts = [0]*(N+1)
cnts[-1] = 3

ans = 1
for a in AA:
    ans *= (cnts[a-1] - cnts[a])
    ans %= mod
    cnts[a] += 1


print(ans)


# Optimized solution
c = [0]*(int(eval(input()))+1)
c[-1] = 3
ans = 1
for a in list(map(int, input().split())):
    ans = (ans * (c[a-1] - c[a]))%(10**9+7)
    c[a] += 1
print(ans)
# Original solution
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
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    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()))


# Optimized solution
M = 1000000007
N = int(eval(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()))
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

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 = (result * k) % 1000000007
print(result)


# Optimized solution
N = int(eval(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)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
MOD = 10**9+7

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


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

ans = 1
dp = [0]*3
for a in A:
    ans = ans*dp.count(a) % MOD
    try:
        dp[dp.index(a)] += 1
    except ValueError:
        break
print(ans)
# Original solution
n = int(eval(input()))
A = list(map(int, input().split()))
mod = 10**9 + 7

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

if n == 1:
    if A[0] == 0:
        print((3))
    else:
        print((0))
    exit()


if A[0] != 0:
    print((0))
    exit()
for a in A[1:]:
    count = hats.count(a)
    if count == 0:
        print((0))
        exit()

    idx = hats.index(a)
    hats[idx] += 1
    ans *= count
    ans %= mod

print(ans)

# Optimized solution
n = int(eval(input()))
A = list(map(int, input().split()))
mod = 10**9 + 7
 
ans = 1
hats = [0, 0, 0]
 
for a in A:
    count = hats.count(a)
    if count == 0:
        print((0))
        exit()
 
    idx = hats.index(a)
    hats[idx] += 1
    ans *= count
    ans %= mod
 
print(ans)
# Original solution
n = int(eval(input()))
A = list(map(int, input().split()))
mod = 10**9 + 7
 
ans = 1
hats = [0, 0, 0]
 
for a in A:
    count = hats.count(a)
    if count == 0:
        print((0))
        exit()
 
    idx = hats.index(a)
    hats[idx] += 1
    ans *= count
    ans %= mod
 
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline
mod = 10**9 + 7

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

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

    print(ans)


if __name__ == "__main__":
    main()
# Original solution
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n,*a=list(map(int,read().split()))
	
	aa=max(a)
	
	li=[[] for _ in range(aa+1)]
	
	for i in range(n):
		li[a[i]].append(i)
	
	if len(li[0])>3 or len(li[0])==0:
		print((0))
		exit(0)
	else:
		ans=3 if len(li[0])==1 else 6
	for i in range(1,aa+1):
		if len(li[i])>3 or len(li[i])==0 or len(li[i])>len(li[i-1]):
			print((0))
			exit(0)
		else:
			k=bisect.bisect_right(li[i-1],li[i][0])
			ans*=k
			ans%=MOD
			
			if len(li[i])>1:
				k=bisect.bisect_right(li[i-1],li[i][1])-1
				ans *= k
				ans %= MOD
		
	print(ans)
	
	
if __name__ == "__main__":
		main()


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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(eval(input()))
def MI(): return list(map(int,input().split()))
def MF(): return list(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()))
# rstrip().decode('utf-8')

#2234
#import numpy as np

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()
# Original solution
import sys
INF = 10 ** 15
MOD = 10 ** 9 + 7
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from math import pi
from functools import lru_cache

def main():
    n = int(eval(input()))
    num = list(map(int,input().split()))
    
    @lru_cache(maxsize = None)
    def dfs(a,b,c):
        if a + b + c == n:
            return 1
        ans = 0
        if num[a + b + c] == a:
            ans += dfs(a + 1,b,c)
            ans %= MOD
        if num[a + b + c] == b:
            ans += dfs(a,b + 1,c)
            ans %= MOD
        if num[a + b + c] == c:
            ans += dfs(a,b,c + 1)
            ans %= MOD
        return ans
    
    print((dfs(0,0,0)))

if __name__ =='__main__':
    main()    

# Optimized solution
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

ans = 1
def dfs(i,x,y,z,a,n):
    global ans
    if i == n:
        return
    if x == y == z == a[i]:
        ans *= 3
        ans %= MOD
        dfs(i + 1,x + 1,y,z,a,n)
    elif x == y == a[i]:
        ans *= 2
        ans %= MOD
        dfs(i + 1,x + 1,y,z,a,n)
    elif y == z == a[i]:
        ans *= 2
        ans %= MOD
        dfs(i + 1,x,y + 1,z,a,n)
    elif x == a[i]:
        dfs(i + 1,x + 1,y,z,a,n)
    elif y == a[i]:
        dfs(i + 1,x,y + 1,z,a,n)
    elif z == a[i]:
        dfs(i + 1,x,y,z + 1,a,n)
    else:
        ans = 0
        return

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

    dfs(0,0,0,0,a,n)
    print(ans)

if __name__ =='__main__':
    main()
# Original solution
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

ans = 1
def dfs(i,x,y,z,a,n):
    global ans
    if i == n:
        return
    if x == y == z == a[i]:
        ans *= 3
        ans %= MOD
        dfs(i + 1,x + 1,y,z,a,n)
    elif x == y == a[i]:
        ans *= 2
        ans %= MOD
        dfs(i + 1,x + 1,y,z,a,n)
    elif y == z == a[i]:
        ans *= 2
        ans %= MOD
        dfs(i + 1,x,y + 1,z,a,n)
    elif x == a[i]:
        dfs(i + 1,x + 1,y,z,a,n)
    elif y == a[i]:
        dfs(i + 1,x,y + 1,z,a,n)
    elif z == a[i]:
        dfs(i + 1,x,y,z + 1,a,n)
    else:
        ans = 0
        return

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

    dfs(0,0,0,0,a,n)
    print(ans)

if __name__ =='__main__':
    main()   


# Optimized solution
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(eval(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()
# Original solution
import sys
input = sys.stdin.readline

n = int(eval(input()))
a = list(map(int, input().split()))
rbg = [-1, -1, -1]
ans = 1
mod = 10 ** 9 + 7

for A in a:
    ans *= rbg.count(A - 1)
    ans %= mod
    for i in range(3):
        if rbg[i] == A - 1:
            rbg[i] = A
            break

print(ans)


# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = list(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)
# Original solution
import sys,queue,math,copy
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in input().split()]
_LI = lambda : [int(x)-1 for x in input().split()]
N = int(eval(input()))
A = LI()


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

# Optimized solution
import sys,queue,math,copy
input = sys.stdin.readline
MOD = 10**9 + 7
LI = lambda : [int(x) for x in input().split()]
N = int(eval(input()))
A = LI()
c =[0,0,0]
cnt = [0 for _ in range(N)]
for i in range(N):
    cnt[i] = c.count(A[i])
    if cnt[i] == 0: break
    c[c.index(A[i])] += 1
ans = 1
for i in range(N):
    ans = (ans * cnt[i]) % MOD
print (ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

c = [-1, -1 ,-1]

sum = 1
tmp = 0
for i in range(N):
    sum = sum * c.count(A[i]-1) % 1000000007
    if (A[i]-1) == c[0]:
        c[0] += 1
        tmp = c.count(c[0] - 1) + 1
    elif (A[i]-1) == c[1]:
        c[1] += 1
        tmp = c.count(c[1]-1) + 1
    elif (A[i]-1) == c[2]:
        c[2] += 1
        tmp = c.count(c[2] - 1) + 1
print(sum)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

c = [-1, -1 ,-1]

sum = 1
tmp = 0
for a in A:
    sum = sum * c.count(a-1) % 1000000007
    if a-1 == c[0]:
        c[0] += 1
        tmp = c.count(c[0] - 1) + 1
    elif a-1 == c[1]:
        c[1] += 1
        tmp = c.count(c[1]-1) + 1
    elif a-1 == c[2]:
        c[2] += 1
        tmp = c.count(c[2] - 1) + 1
print(sum)
# Original solution
def main():
    MOD = 10 ** 9 + 7
    N = int(eval(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()

# Optimized solution
def main():
    N = int(eval(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()
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = 1
cnt = [0, 0, 0]

for i in range(n):
    ans *= cnt.count(a[i])
    if a[i] not in cnt:
        print((0))
        exit()
    ind = cnt.index(a[i])
    cnt[ind] += 1

print((ans % mod))

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = 1
cnt = [0, 0, 0]

for i in a:
    ans *= cnt.count(i)
    ans %= mod
    if i not in cnt:
        print((0))
        exit()
    ind = cnt.index(i)
    cnt[ind] += 1

print(ans)
# Original solution
MOD = 10**9+7
n = int(eval(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))


# Optimized solution
MOD = 10**9+7
n = int(eval(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))
# Original solution
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(eval(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()

# Optimized solution
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(eval(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()
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
mod = 1000000007
colors = [0,0,0]
ans = 1
for i in range(N):
    ans = (ans * colors.count(A[i])) % mod
    for j in range(3):
        if colors[j] == A[i]:
            colors[j] += 1
            break
print(ans)

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

RGB = [0, 0, 0]

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

print(ans)
# Original solution
N = int(eval(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)


# Optimized solution
N, *A = list(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)
# Original solution
mod = 10**9+7
def main():
	ans =1
	n = int(eval(input()))
	arr = list(map(int , input().split()))
	col=[0 for i in range(0 , 6)]
	for i in range(0 , n):
		cnt , cur =0 , -1
		if arr[i]==col[0]:
			cnt = cnt+1
			cur = 0
		if arr[i]==col[1]:
			cnt = cnt+1
			cur = 1
		if arr[i]==col[2]:
			cnt = cnt+1
			cur = 2
		if cur ==-1:
			print((0))
			exit()
		col[cur]=col[cur]+1
		ans = (ans*cnt)%mod
		ans = ans%mod
	print(ans)

if __name__ =="__main__":
	main()

# Optimized solution
# similar to problem if n person are arranged in a row and have 3 different hats to wear
# no of ways of wearing hats so that every adjacent person wears different hats
# so ith person cannot wear more than 3 no of different ways
mod = 10**9+7
def main():
	ans =1
	n = int(eval(input()))
	arr = list(map(int , input().split()))
	col=[0 for i in range(0 , 6)]
	for i in range(0 , n):
		cnt , cur =0 , -1
		if arr[i]==col[0]:
			cnt = cnt+1
			cur = 0
		if arr[i]==col[1]:
			cnt = cnt+1
			cur = 1
		if arr[i]==col[2]:
			cnt = cnt+1
			cur = 2
		if cur ==-1:
			print((0))
			exit()
		col[cur]=col[cur]+1
		ans = (ans*cnt)%mod
		ans = ans%mod
	print(ans)

if __name__ =="__main__":
	main()
# Original solution
import sys
read = sys.stdin.read

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

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

for i in range(N):
    answer *= hats[i].count(A[i])
    answer %= mod
    flag = True
    for j in range(3):
        if hats[i][j] == A[i] and flag:
            hats[i + 1][j] = A[i] + 1
            flag = False
        else:
            hats[i + 1][j] = hats[i][j]

print(answer)

# Optimized solution
import sys
read = sys.stdin.read

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

hats = [0] * 3
answer = 1

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

print(answer)
# Original solution
import copy
n = int(eval(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)

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


# Optimized solution
def main():
    import sys

    MOD = 1000000007
    N, *A = list(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()
# Original solution
def main():
    import sys

    MOD = 1000000007
    N, *A = list(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()


# Optimized solution
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 = list(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()
# Original solution
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 = list(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()


# Optimized solution
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 = list(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()
# Original solution
n=int(eval(input()))
A=[int(i) for i in input().split()]
mod=10**9+7
ans=1
B=[0,0,0]
for i in range(n):
  ct=0
  chk=False
  for j in range(3):
    if B[j]==A[i]:
      ct+=1
      if not chk:
        B[j]+=1
        chk=True
  ans=(ans*ct)%mod
print(ans)



# Optimized solution
import sys
input=lambda: sys.stdin.readline().rstrip()

n=int(eval(input()))
A=[int(i) for i in input().split()]
ans=1
mod=10**9+7
C=[0,0,0]
for i in range(n):
  cur=A[i]
  ct=0
  Chk=True
  for i,c in enumerate(C):
    if cur==c:
      ct+=1
      if Chk:
        C[i]+=1
        Chk=False
  ans=(ans*ct)%mod
  
print(ans)