#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;cin >> n;
vector<int> t2(n),t3(n);
for(int i = 0;i<n;i++){
int a;cin >> a;
t2[i] = 0;
t3[i] = 0;
int temp =a;
while(temp != 0){
if(temp%2 == 1)
t2[i]++;
temp /= 2;
}
temp = a;
while(temp != 0){
if(temp%3 == 1)
t3[i]++;
temp /= 3;
}
}
int dp[n][(1 << n)];
for(int j = 1;j<(1 << n);j++){
for(int i = 0;i<n;i++){
dp[i][j] = 0;
}
}
for(int i = 0;i<n;i++)
dp[i][(1 << i)] = 1;
for(int j = 1;j<(1 << n);j++){
vector<int> selected;
for(int i = 0;i<n;i++){
if(j&(1 << i))
selected.push_back(i);
}
for(int e : selected){
for(int f : selected){
if(e != f){
if(t2[e] == t2[f] || t3[e] == t3[f]){
dp[e][j] += dp[f][j^(1 << e)];
}
}
}
}
}
int ans = 0;
for(int i = 0;i<n;i++)
ans += dp[i][(1 << n) - 1];
cout << ans;
}
signed main(){
iostream::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int T = 1;
//cin >> T;
while(T--){
solve();
}
}
