#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n, x, y; cin >> n;
int b2[n], b3[n];
for(int i=0; i<n; ++i){
b2[i] = b3[i] = 0;
cin >> x;
y = x;
while(y) b2[i] += (y % 2)==1, y /= 2;
while(x) b3[i] += (x % 3)==1, x /= 3;
}
bool d[n][n];
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
d[i][j] = b2[i]==b2[j] or b3[i]==b3[j];
int ans[1<<n][n];
for(int i=0; i<(1<<n); ++i){
for(int j=0; j<n; ++j){
ans[i][j] = 0;
if(i==(1<<j)) ans[i][j] = 1;
}
for(int j=0; j<n; ++j){
for(int k=j+1; k<n; ++k){
if(!(i&(1<<j)) or !(i&(1<<k)) or j==k) continue;
if(d[j][k]){
ans[i][j] += ans[i^(1<<j)][k];
ans[i][k] += ans[i^(1<<k)][j];
}
}
}
}
cout << accumulate(ans[(1<<n)-1], ans[(1<<n)-1]+n, 0LL);
}
