MOD = 10**9 + 7





class modint():

    def __init__(self, value):

        self.value = value % MOD



    def __int__(self):

        return int(self.value)



    def __float__(self):

        return float(self.value)



    def __str__(self):

        return str(self.value)



    def __repr__(self):

        return str(self.value)



    def __add__(self, other):

        return (modint(self.value + other.value) if isinstance(other, modint)

                else modint(self.value + other))



    def __sub__(self, other):

        return (modint(self.value - other.value) if isinstance(other, modint)

                else modint(self.value - other))



    def __mul__(self, other):

        return (modint(self.value * other.value) if isinstance(other, modint)

                else modint(self.value * other))



    def __truediv__(self, other):

        return (modint(self.value * pow(other.value, MOD - 2, MOD))

                if isinstance(other, modint)

                else modint(self.value * pow(other, MOD - 2, MOD)))



    def __pow__(self, other):

        return (modint(pow(self.value, other.value, MOD))

                if isinstance(other, modint)

                else modint(pow(self.value, other, MOD)))



    def __eq__(self, other):

        return (self.value == other.value if isinstance(other, modint)

                else self.value == (other % MOD))



    def __ne__(self, other):

        return (self.value == other.value if isinstance(other, modint)

                else self.value == (other % MOD))



    def __radd__(self, other):

        return (modint(other.value + self.value) if isinstance(other, modint)

                else modint(other + self.value))



    def __rsub__(self, other):

        return (modint(other.value - self.value) if isinstance(other, modint)

                else modint(other - self.value))



    def __rmul__(self, other):

        return (modint(other.value * self.value) if isinstance(other, modint)

                else modint(other * self.value))



    def __rtruediv__(self, other):

        return (modint(other.value * pow(self.value, MOD - 2, MOD))

                if isinstance(other, modint)

                else modint(other * pow(self.value, MOD - 2, MOD)))



    def __rpow__(self, other):

        return (modint(pow(other.value, self.value, MOD))

                if isinstance(other, modint)

                else modint(pow(other, self.value, MOD)))



    def modinv(self):

        return modint(pow(self.value, MOD - 2, MOD))





def main():

    _ = int(input())

    A = [int(i) for i in input().split()]

    from collections import defaultdict

    d = defaultdict(int)

    ans = modint(0)

    for a in A:

        d[a] += 1

        if (a != 0 and d[a-1] < d[a]) or 3 < d[a]:

            return print(0)

        if a == 0:

            if d[a] == 1:

                ans += 1

            elif d[a] == 2:

                ans *= 2

            continue

        if d[a] == 1:

            ans *= d[a-1]

        elif d[a] == 2:

            ans *= d[a-1] - 1



    print((ans*3))





if __name__ == '__main__':

    main()

MOD = 10**9 + 7





def main():

    N = int(eval(input()))

    A = [int(i) for i in input().split()]

    B = [0]*N

    ans = 3

    for a in A:

        if a == 0:

            if B[a] == 1:

                ans *= 2

        else:

            ans *= B[a-1] - B[a]

        B[a] += 1

        if 3 < B[a] or (a != 0 and B[a-1] < B[a]):

            ans = 0

            break

        ans %= MOD

    print(ans)





if __name__ == '__main__':

    main()

MOD = 10**9 + 7


class modint:
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (
            modint(self.value + other.value)
            if isinstance(other, modint)
            else modint(self.value + other)
        )

    def __sub__(self, other):
        return (
            modint(self.value - other.value)
            if isinstance(other, modint)
            else modint(self.value - other)
        )

    def __mul__(self, other):
        return (
            modint(self.value * other.value)
            if isinstance(other, modint)
            else modint(self.value * other)
        )

    def __truediv__(self, other):
        return (
            modint(self.value * pow(other.value, MOD - 2, MOD))
            if isinstance(other, modint)
            else modint(self.value * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            modint(pow(self.value, other.value, MOD))
            if isinstance(other, modint)
            else modint(pow(self.value, other, MOD))
        )

    def __eq__(self, other):
        return (
            self.value == other.value
            if isinstance(other, modint)
            else self.value == (other % MOD)
        )

    def __ne__(self, other):
        return (
            self.value == other.value
            if isinstance(other, modint)
            else self.value == (other % MOD)
        )

    def __radd__(self, other):
        return (
            modint(other.value + self.value)
            if isinstance(other, modint)
            else modint(other + self.value)
        )

    def __rsub__(self, other):
        return (
            modint(other.value - self.value)
            if isinstance(other, modint)
            else modint(other - self.value)
        )

    def __rmul__(self, other):
        return (
            modint(other.value * self.value)
            if isinstance(other, modint)
            else modint(other * self.value)
        )

    def __rtruediv__(self, other):
        return (
            modint(other.value * pow(self.value, MOD - 2, MOD))
            if isinstance(other, modint)
            else modint(other * pow(self.value, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            modint(pow(other.value, self.value, MOD))
            if isinstance(other, modint)
            else modint(pow(other, self.value, MOD))
        )

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    _ = int(input())
    A = [int(i) for i in input().split()]
    from collections import defaultdict

    d = defaultdict(int)
    ans = modint(0)
    for a in A:
        d[a] += 1
        if (a != 0 and d[a - 1] < d[a]) or 3 < d[a]:
            return print(0)
        if a == 0:
            if d[a] == 1:
                ans += 1
            elif d[a] == 2:
                ans *= 2
            continue
        if d[a] == 1:
            ans *= d[a - 1]
        elif d[a] == 2:
            ans *= d[a - 1] - 1
    print((ans * 3))


if __name__ == "__main__":
    main()

MOD = 10**9 + 7


def main():
    N = int(eval(input()))
    A = [int(i) for i in input().split()]
    B = [0] * N
    ans = 3
    for a in A:
        if a == 0:
            if B[a] == 1:
                ans *= 2
        else:
            ans *= B[a - 1] - B[a]
        B[a] += 1
        if 3 < B[a] or (a != 0 and B[a - 1] < B[a]):
            ans = 0
            break
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

-class modint: -    def __init__(self, value): -        self.value = value % MOD - -    def __int__(self): -        return int(self.value) - -    def __float__(self): -        return float(self.value) - -    def __str__(self): -        return str(self.value) - -    def __repr__(self): -        return str(self.value) - -    def __add__(self, other): -        return ( -            modint(self.value + other.value) -            if isinstance(other, modint) -            else modint(self.value + other) -        ) - -    def __sub__(self, other): -        return ( -            modint(self.value - other.value) -            if isinstance(other, modint) -            else modint(self.value - other) -        ) - -    def __mul__(self, other): -        return ( -            modint(self.value * other.value) -            if isinstance(other, modint) -            else modint(self.value * other) -        ) - -    def __truediv__(self, other): -        return ( -            modint(self.value * pow(other.value, MOD - 2, MOD)) -            if isinstance(other, modint) -            else modint(self.value * pow(other, MOD - 2, MOD)) -        ) - -    def __pow__(self, other): -        return ( -            modint(pow(self.value, other.value, MOD)) -            if isinstance(other, modint) -            else modint(pow(self.value, other, MOD)) -        ) - -    def __eq__(self, other): -        return ( -            self.value == other.value -            if isinstance(other, modint) -            else self.value == (other % MOD) -        ) - -    def __ne__(self, other): -        return ( -            self.value == other.value -            if isinstance(other, modint) -            else self.value == (other % MOD) -        ) - -    def __radd__(self, other): -        return ( -            modint(other.value + self.value) -            if isinstance(other, modint) -            else modint(other + self.value) -        ) - -    def __rsub__(self, other): -        return ( -            modint(other.value - self.value) -            if isinstance(other, modint) -            else modint(other - self.value) -        ) - -    def __rmul__(self, other): -        return ( -            modint(other.value * self.value) -            if isinstance(other, modint) -            else modint(other * self.value) -        ) - -    def __rtruediv__(self, other): -        return ( -            modint(other.value * pow(self.value, MOD - 2, MOD)) -            if isinstance(other, modint) -            else modint(other * pow(self.value, MOD - 2, MOD)) -        ) - -    def __rpow__(self, other): -        return ( -            modint(pow(other.value, self.value, MOD)) -            if isinstance(other, modint) -            else modint(pow(other, self.value, MOD)) -        ) - -    def modinv(self): -        return modint(pow(self.value, MOD - 2, MOD)) - - -    _ = int(input()) +    N = int(eval(input())) -    from collections import defaultdict - -    d = defaultdict(int) -    ans = modint(0) +    B = [0] * N +    ans = 3 -        d[a] += 1 -        if (a != 0 and d[a - 1] < d[a]) or 3 < d[a]: -            return print(0) -            if d[a] == 1: -                ans += 1 -            elif d[a] == 2: +            if B[a] == 1: -            continue -        if d[a] == 1: -            ans *= d[a - 1] -        elif d[a] == 2: -            ans *= d[a - 1] - 1 -    print((ans * 3)) +        else: +            ans *= B[a - 1] - B[a] +        B[a] += 1 +        if 3 < B[a] or (a != 0 and B[a - 1] < B[a]): +            ans = 0 +            break +        ans %= MOD +    print(ans)