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


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