#include<bits/stdc++.h>
using namespace std;
int n,k,b,ones[2][25],cur,a[25],dp[2000005][25],ans;
int main(){
cin>>n;
for(k=0;k<n;k++){
cin>>a[k];
b=a[k];
while(b){
if(b%2) ones[0][k]++;
b/=2;
}
b=a[k];
while(b){
if(b%3==1) ones[1][k]++;
b/=3;
}
dp[1<<k][k]=1;
}
for(k=1;k<(1<<n);k++){
for(int j=0;j<n;j++){
b=1<<j;
if(! (b&k)) continue;
cur=k^b;
for(int i=0;i<n;i++){
b=1<<i;
if(!(b&cur)) continue;
// cout<<k<<" "<<i<<" "<<j<<endl;
if(ones[0][j]==ones[0][i] || ones[1][j]==ones[1][i]){
dp[k][j]+=dp[cur][i];// cout<<cur<<" "<<i<<endl;
} }
// cout<<k<<"_"<<j<<" "<<dp[k][j]<<endl;
if(k == ((1<<n) -1)) ans+=dp[k][j];
} }
cout<<ans;
}
