#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <functional>
#include <math.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define INF ((int)1e9)
#define INFLL ((ll)1e18)
#define MOD (1000000007LL)

class mod {
public:
    mod() {m_n = 0;}
    mod(ll n) {if (n >= 0) m_n = n % MOD; else m_n = n % MOD + MOD;}
    friend bool operator== (const mod& a, const mod& b) {return a.m_n == b.m_n;}
    friend bool operator!= (const mod& a, const mod& b) {return !(a == b);}
    friend mod operator+ (const mod& a, const mod& b) {return (a.m_n + b.m_n) % MOD;}
    friend mod& operator+= (mod& a, const mod& b) {return a = a + b;}
    friend mod operator- (const mod& a) {return -a.m_n;}
    friend mod operator- (const mod& a, const mod& b) {return (a.m_n + (-b.m_n)) % MOD;}
    friend mod& operator-= (mod& a, const mod& b) {return a = a - b;}
    friend mod operator* (const mod& a, const mod& b) {return (a.m_n * b.m_n) % MOD;}
    friend mod& operator*= (mod& a, const mod& b) {return a = a * b;}
    friend mod mod_pow(const mod& n, ll r) {
        if (r == 0) {
            return 1;
        } else if (r < 0) {
            return mod_pow(n, (MOD - 2) * (-r));
        } else if (r % 2 == 0) {
            mod tmp = mod_pow(n, r / 2);
            return tmp * tmp;
        } else {
            return n * mod_pow(n, r - 1);
        }
    }
    friend mod operator/ (const mod& a, const mod& b) {return a * mod_pow(b, -1);}
    friend mod& operator/= (mod& a, const mod& b) {return a = a / b;}
    friend ostream& operator<< (ostream& os, const mod& n) {os << n.m_n; return os;}
    friend istream& operator>> (istream& is, mod& n) {ll tmp; is >> tmp; n = mod(tmp); return is;}
private:
    ll m_n;
};

#define FACT_MAX 100005
mod fact[FACT_MAX], fact_inv[FACT_MAX];
void prep_fact(int N)
{
    fact[0] = 1;
    for (int n = 1; n <= N; ++n) {
        fact[n] = n * fact[n-1];
    }
}
void prep_fact_inv(int N)
{
    for (int n = 0; n <= N; ++n) {
        fact_inv[n] = mod_pow(fact[n], -1);
    }
}
void prep(int N)
{
    prep_fact(N);
    prep_fact_inv(N);
}
mod comb(int n, int k) {if (n < 0 || k < 0 || k > n) return 0; else return fact[n] * fact_inv[n-k] * fact_inv[k];}
mod multi_choose(int n, int k) {return comb(n + k - 1, k);}

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int n = 0; n < N; ++n) cin >> A[n];
    
    int ac[3] = {0, 0, 0};
    mod ret = 1;
    for (int n = 0; n < N; ++n) {
        if (A[n] == ac[0]) {
            if (A[n] == ac[1]) {
                if (A[n] == ac[2]) {
                    ret *= 3;
                } else {
                    ret *= 2;
                }
            }
            ++ac[0];
        } else if (A[n] == ac[1]) {
            if (A[n] == ac[2]) {
                ret *= 2;
            }
            ++ac[1];
        } else if (A[n] == ac[2]){
            ++ac[2];
        } else {
            cout << 0 << endl;
            return 0;
        }
    }
    cout << ret << endl;

    return 0;
}


Measured memory_bytes: 2176