#include <stdio.h>
#define N_MAX 20
#define BIT_MAX 1048575
int N, M=1, A[N_MAX+1], B[N_MAX+1][N_MAX+1];
long long D[N_MAX+1][BIT_MAX+1], Ans;
int binaryOne(int num) {
int i, cnt=0;
for(i=1 ; i<=num ; i<<=1)
if(num&i)
cnt++;
return cnt;
}
int ternaryOne(int num) {
int cnt=0;
while(num) {
if(num%3==1)
cnt++;
num/=3;
}
return cnt;
}
int main(void) {
int i, j, k;
scanf("%d",&N);
for(i=1 ; i<=N ; i++)
scanf("%d",&A[i]);
for(i=1 ; i<=N ; i++)
for(j=1 ; j<=N ; j++)
if(i!=j && (binaryOne(A[i])==binaryOne(A[j]) || ternaryOne(A[i])==ternaryOne(A[j])))
B[i][j]=1;
for(i=1 ; i<=N ; i++) {
M<<=1;
D[i][1<<(i-1)]=1;
}
M--;
for(i=1 ; i<=M ; i++)
for(j=1 ; j<=N ; j++)
if(i&(1<<(j-1)))
for(k=1 ; k<=N ; k++)
if(B[j][k] && i&(1<<(k-1)))
D[j][i]+=D[k][i-(1<<(j-1))];
for(i=1 ; i<=N ; i++)
Ans+=D[i][M];
printf("%lld",Ans);
return 0;
}
