#include <iostream>
using namespace std;
long long dp[(1<<20)+1][21];
long long ans;
int a[25],b[25];
int n,x,i,j,k;
int cnt(int x,int b)
{
int ret=0;
while(x)
{
ret+=(x%b==1);
x/=b;
}
return ret;
}
int main()
{
cin>>n;
for(i=0;i<n;i++)
{
cin>>x;
a[i]=cnt(x,2);
b[i]=cnt(x,3);
}
for(i=0;i<n;i++)
dp[(1<<i)][i]=1;
for(i=0;i<(1<<n);i++)
for(j=0;j<n;j++)
if(((1<<j)&i))
for(k=0;k<n;k++)
if((a[j]==a[k]||b[j]==b[k])&&(!((1<<k)&i)))
dp[(1<<k)+i][k]+=dp[i][j];
for(i=0;i<n;i++)
ans+=dp[(1<<n)-1][i];
cout<<ans;
return 0;
}
