#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = INT_MAX;
constexpr ll L_INF = LLONG_MAX;

//===



constexpr int64_t MOD = static_cast<int64_t>(1e9 + 7);



// ModInt
//
// 宣言:
// ModInt<1000000007> mi;
// ModInt<1000000007> mi(917856986);
//
template <std::int_fast64_t Modulus>
class ModInt
{
	using i64 = std::int_fast64_t;

public:
	i64 a;

	constexpr ModInt(const i64 x = 0) noexcept : a(x% Modulus) {}

	constexpr i64& value() noexcept { return a; }
	constexpr const i64& value() const noexcept { return a; }

	constexpr ModInt operator+(const ModInt& rhs) const noexcept
	{
		return ModInt(*this) += rhs;
	}
	constexpr ModInt operator-(const ModInt& rhs) const noexcept
	{
		return ModInt(*this) -= rhs;
	}
	constexpr ModInt operator*(const ModInt& rhs) const noexcept
	{
		return ModInt(*this) *= rhs;
	}
	constexpr ModInt operator/(const ModInt& rhs) const noexcept
	{
		return ModInt(*this) /= rhs;
	}

	constexpr ModInt& operator+=(const ModInt rhs) noexcept
	{
		a += rhs.a;
		if (a >= Modulus) {
			a -= Modulus;
		}
		return *this;
	}
	constexpr ModInt& operator-=(const ModInt rhs) noexcept
	{
		if (a < rhs.a) {
			a += Modulus;
		}
		a -= rhs.a;
		return *this;
	}
	constexpr ModInt& operator*=(const ModInt rhs) noexcept
	{
		a = a * rhs.a % Modulus;
		return *this;
	}
	constexpr ModInt& operator/=(ModInt rhs) noexcept
	{
		i64 exp = Modulus - 2;
		while (exp) {
			if (exp & 1) {
				*this *= rhs;
			}
			rhs *= rhs;
			exp >>= 1;
		}
		return *this;
	}

	constexpr ModInt& operator++() noexcept
	{
		*this += 1;
		return *this;
	}
	constexpr ModInt operator++(int) noexcept
	{
		ModInt res = *this;
		*this += 1;
		return res;
	}
	constexpr ModInt& operator--() noexcept
	{
		*this -= 1;
		return *this;
	}
	constexpr ModInt operator--(int) noexcept
	{
		ModInt res = *this;
		*this -= 1;
		return res;
	}

	constexpr bool operator<(const ModInt& rhs) const noexcept
	{
		return a < rhs.a;
	}
	constexpr bool operator>(const ModInt& rhs) const noexcept
	{
		return a > rhs.a;
	}
	constexpr bool operator<=(const ModInt& rhs) const noexcept
	{
		return a <= rhs.a;
	}
	constexpr bool operator>=(const ModInt& rhs) const noexcept
	{
		return a >= rhs.a;
	}
	constexpr bool operator==(const ModInt& rhs) const noexcept
	{
		return a == rhs.a;
	}

	constexpr ModInt pow(i64 k) const noexcept
	{
		ModInt res = 1;
		ModInt tmp = *this;
		for (; k > 0; k >>= 1) {
			if (k & 1) res *= tmp;
			tmp *= tmp;
		}
		return res;
	}

	constexpr ModInt inverse() const noexcept
	{
		i64 q = a;
		i64 b = Modulus, u = 1, v = 0;
		while (b) {
			i64 t = q / b;
			q -= t * b;
			swap(q, b);
			u -= t * v;
			swap(u, v);
		}
		u %= Modulus;
		if (u < 0) u += Modulus;
		return u;
	}
};







int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	ll N; cin >> N;
	Vl A(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}

	ModInt<MOD> ans = 1;
	map<ll, ll> mp;

	for (int i = 0; i < N; ++i) {
		if (A[i] == 0) {
			ans *= 3 - mp[A[i]];
		}
		else {
			ans *= mp[A[i] - 1] - mp[A[i]];
		}
		++mp[A[i]];
	}

	cout << ans.value() << endl;

	return 0;
}

Measured memory_bytes: 7296