#include <bits/stdc++.h>
using namespace std;
long long d[(1<<20)+5][25],ans;
int a2[25],a3[25],x,i,j,bm,n;
int main(){
cin>>n;
for (i=0; i<n; i++){
cin>>x; d[1<<i][i]=1;
a2[i]=__builtin_popcount(x);
while (x>0){
if (x%3==1) a3[i]++;
x/=3;
}
}
//for (i=0; i<n; i++) cout<<a2[i]<<' '<<a3[i]<<'\n';
for (bm=0; bm<(1<<n); bm++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
if ((1<<i)&bm && (1<<j)&bm && i!=j)
if (a2[i]==a2[j] || a3[i]==a3[j])
d[bm][i]+=d[bm-(1<<i)][j];
for (i=0; i<n; i++)
ans+=d[(1<<n)-1][i];
cout<<ans;
}
