#include <bits/stdc++.h>
#define N 20
using namespace std;
int bin[N];
int ter[N];
long long dp[(1<<N)][N];
void solve(){
int n;
cin >> n;
for(int i=0;i<n;i++){
int x;
cin >> x;
int tmp = x;
while(x){
bin[i] += (x%2) == 1;
x /= 2;
}
while(tmp){
ter[i] += (tmp%3) == 1;
tmp /= 3;
}
}
int num = 1,pw = 0;
for(int mask = 1;mask < (1<<n);mask++){
if(mask == num){
dp[mask][pw++] = 1;
num *= 2;
}
for(int i=0;i<n;i++){
if(mask & (1<<i)){
for(int j = 0;j<n;j++){
if(mask & (1<<j)){
if(bin[i] == bin[j] || ter[i] == ter[j])
dp[mask][i] += dp[mask ^ (1<<i)][j];
}
}
}
}
}
long long ans = 0;
for(int i=0;i<n;i++){
ans += dp[(1<<n) - 1][i];
}
cout << ans;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
