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

using i64 = long long;

const int P = 1e9 + 7;

int c[3];

int check(int x) {
    if(c[x] == 0) return 0;
    vector<int> b(3);
    b[x] ++;
    while(c[1] + c[2] - b[1] - b[2]) {
        if(b[x] + 1 > c[x]) return 0;
        b[x] ++;
        x ^= 3;
    }
    return 1;
}

int fact(int l, int r) {
    int ret = 1;
    while(l <= r) {
        ret = ret * (i64)l % P;
        l ++;
    }
    return ret;
}

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

    int n;
    cin >> n;
    for(int i = 1, x; i <= n; i ++) {
        cin >> x;
        c[x % 3] ++;
    }

    cout << (check(1) + check(2)) * (i64)fact(1, c[1]) * fact(1, c[2]) % P * fact(c[1] + c[2], n - 1) % P << "\n";
}

/*
2
5 2
1 3 3 2 2
4 3
1 4 2 1
*/