#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn=20;
const int B = (1<<20);
int n;
ll dp[B][maxn];
int a[maxn],jog[maxn][maxn];
int ok(int x,int y){
int cp = 0,sg = 0;
int nwx = x,nwy = y;
while(nwx){
cp += (nwx%2);
nwx /= 2;
}
while(nwy){
sg += (nwy%2);
nwy /= 2;
}
// if(x == 5 and y == 6) cout<<cp<<' '<<sg<<'\n';
if(cp == sg) return 1;
cp = sg = 0;
while(x){
cp += ((x%3) == 1);
x /= 3;
}
while(y){
sg += ((y%3) == 1);
y /= 3;
}
return (cp == sg);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 0;i < n;i++){
cin >> a[i];
dp[(1<<i)][i] = 1;
}
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
int nw = ok(a[i],a[j]);
jog[i][j] = jog[j][i] = nw;
}
}
// cout<<jog[0][2]<<'\n';
int go = (1<<n);
for(int i = 3;i < go;i++){
vector<int>nw;
for(int j = 0;j < n;j++) if((1<<j) & i) nw.push_back(j);
for(int j = 0;j < (int)nw.size();j++){
int now = i ^ (1<<nw[j]);
for(int k = 0;k < (int)nw.size();k++){
if(j == k or !jog[nw[j]][nw[k]]) continue;
dp[i][nw[j]] += dp[now][nw[k]];
}
}
}
ll ans = 0;
for(int i = 0;i < n;i++) ans += dp[go - 1][i];
// for(int i = 1;i < go;i++){
// cout<<i<<" ---> ";
// for(int j = 0;j < n;j++) cout<<dp[i][j]<<' ';
// cout<<'\n';
// }
cout<<ans;
}
