#include <bits/stdc++.h>
#define MAX 1100000
using ll = long long;
ll getval(ll x,ll t){
ll ans=0;
while(x){
ll p = x%t;
if(p==1)++ans;
x/=t;
}
return ans;
}
long long ind[21][2];
bool existe[MAX][20];
ll tab[MAX][20];
ll obj=0;
int N;
ll dp(ll pente,int pos){
if(pente==obj)return 1;
if(existe[pente][pos])return tab[pente][pos];
existe[pente][pos]=true;
ll tot=0;
for(int i=0;i!=N;++i){
if(pente&(1<<i))continue;
if(ind[pos][0]==ind[i][0]
||ind[pos][1]==ind[i][1]){
tot+=dp(pente+(1<<i),i);
}
}
return tab[pente][pos]=tot;
}
int main()
{
std::cin>>N;
obj=(1<<N)-1;
for(int i=0;i!=N;++i){
ll x;std::cin>>x;
ind[i][0]=getval(x,2);
ind[i][1]=getval(x,3);
}
ll ans=0;
for(int i=0;i!=N;++i){
ans+=dp(1<<i,i);
}
std::cout<<ans<<"\n";
}
