#include<iostream>
#include<algorithm>
using namespace std;
int n;
int cnt2[25];
int cnt3[25];
long long dp[1100000][20];
int calc_cnt2(int x)
{
int rez=0;
for(int i=0;i<30;i++)
{
if(((1<<i)&x))
rez++;
}
return rez;
}
int calc_cnt3(int x)
{
int rez=0;
while(x>0)
{
if(x%3==1)
rez++;
x/=3;
}
return rez;
}
signed main()
{
cin>>n;
int a;
for(int i=0;i<n;i++)
{
cin>>a;
cnt2[i] = calc_cnt2(a);
cnt3[i] = calc_cnt3(a);
}
for(int config=1;config<(1<<n);config++)
{
for(int cur=0;cur<n;cur++)
{
if(((1<<cur)&config)==0)
continue;
int cate=0;
for(int ult=0;ult<n;ult++)
{
if(ult!=cur && ((1<<ult)&config))
{
cate++;
if(cnt2[ult]==cnt2[cur] || cnt3[ult]==cnt3[cur])
{
dp[config][cur] += dp[config-(1<<cur)][ult];
}
}
}
if(cate==0)
dp[config][cur] = 1;
}
}
long long sum=0;
for(int ult=0;ult<n;ult++)
sum += dp[(1<<n)-1][ult];
cout<<sum;
return 0;
}
