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

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

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

+input = sys.stdin.readline -inputs = sys.stdin.buffer.readlines +# 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())) + + -# INF=float("inf") -MOD = 10**9 + 7 -# sys.setrecursionlimit(2147483647) -# import math +# 2234 -# 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()) -    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 +    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