#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma target("tune=native")
#pragma GCC target("avx2")
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define inf 2e9
#define ff first
#define ss second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int N = 20;
vector <short int> v[N];
short int n;
int a[N];
short int c1[N], c2[N];
void get_cnt(int x, int ind){
int _c1 = 0, _c2 = 0;
int X = x;
while (x){
if (x % 2 == 1) _c1++;
x>>=1;
}
x = X;
while (x){
if (x % 3 == 1) _c2++;
x /= 3;
}
c1[ind] = _c1;
c2[ind] = _c2;
return;
}
ll dp[(1<<20)][20];
ll get_dp(int mask, short int lst){
if (mask == ((1<<n)-1)) return 1;
if (dp[mask][lst] != -1)
return dp[mask][lst];
ll ans = 0;
for (auto u: v[lst]){
if (mask & (1<<u)) continue;
ans += get_dp(mask | (1<<u), u);
}
return dp[mask][lst] = ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++)
get_cnt(a[i], i);
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++){
if (c1[i]==c1[j]||c2[i]==c2[j]){
v[i].pb(j);
v[j].pb(i);
}
}
}
ll ans = 0;
memset(dp, -1, sizeof dp);
for (int i = 0; i < n; i++){
ans += get_dp((1<<i), i);
}
cout << ans;
return 0;
}
