#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
int a[20];
int dp[1<<20][20];
bool vis[20][20];
bool check(int a, int b){
int x=0,y=0,l=0,r=0;
int ta=a;
while(ta>0){
x+= (ta%2==1);
ta/=2;
}
ta=a;
while(ta>0){
y+= (ta%3==1);
ta/=3;
}
int tb=b;
while(tb>0){
l+= (tb%2==1);
tb/=2;
}
tb=b;
while(tb>0){
r+= (tb%3==1);
tb/=3;
}
return (x==l or y==r);
}
signed main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int x=a[i],y=a[j];
vis[i][j]=check(x,y);
}
}
for(int i=1;i<(1<<n);i++){
vector<int>v,vc;
for(int j=0;j<n;j++){
if(i & (1<<j)){
v.pb(j);
}
else{
vc.pb(j);
}
}
if(v.size()==1){
dp[1<<v[0]][v[0]]=1;
}
for(auto a:v){
for(auto b:vc){
if(vis[a][b]){
dp[i+(1<<b)][b]+=dp[i][a];
}
}
}
}
//2 0 1
int s=0;
for(int i=0;i<n;i++){
s+=dp[(1<<n)-1][i];
}
cout<<s;
}
