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

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

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

-    c = [0, 0, 0] +    c = [3] + [0] * 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) +        p = a[i] +        ans = ans * c[p] % MOD +        c[p] -= 1 +        c[p + 1] += 1