#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=21, kx=(1<<20)+5;
ll n, a[nx], dp[nx][kx], x[nx], y[nx], res;
vector<int> d[nx];
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n;
for (int i=0; i<n; i++)
{
cin>>a[i];
int tmp=a[i];
while (tmp>0) x[i]+=((tmp%2)==1), tmp/=2;
tmp=a[i];
while (tmp>0) y[i]+=((tmp%3)==1), tmp/=3;
}
for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) if (x[i]==x[j]||y[i]==y[j]) d[i].push_back(j), d[j].push_back(i); //cout<<"edge "<<i<<' '<<j<<'\n';
for (int i=1; i<(1<<n); i++)
{
for (int u=0; u<n; u++)
{
if (!(i&(1<<u))) continue;
if (__builtin_popcount(i)==1)
{
dp[u][i]=1;
continue;
}
for (auto v:d[u])
{
if (i&(1<<v))
{
dp[u][i]+=dp[v][i^(1<<u)];
}
}
//cout<<"debug "<<i<<' '<<u<<' '<<dp[u][i]<<'\n';
}
}
for (int i=0; i<n; i++) res+=dp[i][(1<<n)-1];
cout<<res;
}
