#include<vector>
#include<iostream>
#include <stdlib.h>
#include <algorithm>
#include <stack>
#include <string.h>
using namespace std;
long long dp[1<<20][20];
int N;
vector<int> a;
int ones(int x, int base){
int ans = 0;
while (x > 0){
if (x % base == 1) ans++;
x /= base;
}
return ans;
}
bool works(int a, int b){
return ones(a, 2) == ones(b,2) || ones(a, 3) == ones(b, 3);
}
long long ways(int S, int last){
if (dp[S][last] != -1) return dp[S][last];
if (S == (1<<N) - 1) return 1;
long long ans = 0;
for (int i=0;i<N;i++){
if ((S & (1<<i)) != 0) continue;
if (works(a[last], a[i])) ans += ways(S + (1<<i), i);
}
return dp[S][last] = ans;
}
int main(){
memset(dp, -1, sizeof(dp));
cin >> N;
a.assign(N, 0);
for (int i=0;i<N;i++)
cin >> a[i];
long long total = 0;
for (int i=0;i<N;i++)
total += ways(1<<i, i);
cout << total << endl;
return 0;
}
