#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 20;
const int MAXL = (1 << 20);
ll dp[MAXN][MAXL];
int adj[MAXN],qtd[MAXN][2],alvo,n;
ll solve(int pos,int bitmask){
if(bitmask == alvo){
return 1;
}
if(dp[pos][bitmask] != -1) return dp[pos][bitmask];
ll tot = 0;
for(int nxt = 0;nxt<n;nxt++){
if(((1 << nxt) & adj[pos]) && !((1 << nxt) & bitmask) ){
tot += solve(nxt, (bitmask) | (1 << nxt) );
}
}
return dp[pos][bitmask] = tot;
}
int main(){
cin >> n;
alvo = (1 << n) - 1;
for(int i = 0;i<n;i++) memset(dp[i],-1,sizeof(dp[i]));
for(int i = 0;i<n;i++){
int x;
cin >> x;
int copia = x;
int copia2 = x;
for(int vez = 0;vez<31;vez++){
if(copia % 2 == 1) qtd[i][0]++;
copia /= 2;
if(copia2 % 3 == 1) qtd[i][1]++;
copia2 /= 3;
}
for(int j = 0;j<i;j++){
if(qtd[i][0] == qtd[j][0]){
adj[j] |= (1 << i);
adj[i] |= (1 << j);
}
if(qtd[i][1] == qtd[j][1]){
adj[j] |= (1 << i);
adj[i] |= (1 << j);
}
}
}
ll tot = 0;
for(int i = 0;i<n;i++) tot += solve(i,(1<<i));
cout << tot << endl;
return 0;
}
