#include<bits/stdc++.h>
using namespace std;

const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;

#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); ++i)
#define RFOR(i,r,n) for(ll i = (ll)(n-1); i >= r; --i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()

#define cout cout << setprecision(12)

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;
using vp = vector<pair<ll, ll>>;
using vs = vector<string>;
using vc = vector<char>;
using lst = list<ll>;
using pq = priority_queue<ll>;

template < typename T >
inline void dbg(T a) { cout << a << ' ' << endl; }

/*--------------------template--------------------*/

// Mod-Int
template< int mod >
struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool   operator==(const ModInt &p) const { return x == p.x; }
    bool   operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }
    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }
    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }
    static int get_mod() { return mod; }
};
using modint = ModInt< MOD >;

/*--------------------template--------------------*/

ll n;
modint ans = 1;
int tmp, c1 = 0, c2 = 0, c3 = 0;

int main() {
    cin >> n;
	ll A[n];
	REP(i,n) { cin >> A[i]; }
	//int color[n] = { 0 };

	REP(i,n) {
    	if (A[i] == c1 && A[i] == c2 && A[i] == c3) {
            ans *= 3;
            c1++;
            continue;
        } else if (A[i] == c1 && A[i] == c2) {
            ans *= 2;
            c1++;
            continue;
        } else if (A[i] == c2 && A[i] == c3) {
            ans *= 2;
            c2++;
            continue;
        } else if (A[i] == c3 && A[i] == c1) {
            ans *= 2;
            c3++;
            continue;
        } else if (A[i] == c1) {
            //ans *= 1;
            c1++;
            continue;
        } else if (A[i] == c2) {
            //ans *= 1;
            c2++;
            continue;
        } else if (A[i] == c3) {
            //ans *= 1;
            c3++;
            continue;
        } else {
        	dbg(0);
        	return 0;
        }
    }
	dbg(ans);
}


Measured memory_bytes: 1024