#include<stdio.h>
typedef long long ll;
ll dp[1<<20][20],ans;
int inp[22],n;
bool chk[22][22];
int data[2][22];
int count1(int x,int y)
{
int ret = 0;
while(x){
ret += (x%y==1);
x/=y;
}
return ret;
}
int main(){
scanf("%d",&n);
int i;
for(i=0;i<n;i++)scanf("%d",inp+i);
for(i=0;i<n;i++)data[0][i] = count1(inp[i],2), data[1][i] = count1(inp[i],3);
for(i=0;i<n;i++)for(int j=0;j<n;j++)chk[i][j] = (data[0][i]==data[0][j] || data[1][i]==data[1][j]);
for(i=0;i<n;i++)dp[0][i]=1;
for(int b=0;b<1<<n;b++){
for(i=0;i<n;i++){
if(b&1<<i)continue;
for(int j=0;j<n;j++){
if((b|1<<i) & 1<<j)continue;
if(chk[i][j])dp[b|1<<i][j] += dp[b][i];
}
if((b|1<<i)+1 == 1<<n)ans += dp[b][i];
}
}
printf("%lld",ans);
return 0;
}
