#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define int long long
#define endl '\n'
using namespace std;
const int maxn = 1e6 + 5;
const int inf = 1e9 + 5;
// bool is(int i, int j, vector<int> a){
// }
signed main(){
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
vector<int> t(n);
vector<int> b(n);
vector<int> adj[n];
for(int i = 0; i < n; i++){
b[i] = __builtin_popcount(a[i]);
while(a[i] > 0){
if(a[i] % 3 == 1){
t[i] += 1;
}
a[i] = a[i] / 3;
}
}
// dp[mask][t]
vector<vector<int>> dp((1 << n), vector<int>(n));
auto is = [&](int i, int j){
if(t[i] == t[j] || b[i] == b[j]){
return true;
}
return false;
};
for(int i = 0; i < (1 << n); i++){
if(__builtin_popcount(i) == 1){
dp[i][__lg(i)] = 1;
}
}
for(int i = 1; i < (1 << n); i++){
for(int j = 0; j < n; j++){
if(i & (1 << j)) continue;
int T = i | (1 << j);
for(int k = 0; k < n; k++){
if(i & (1 << k) && is(j, k)){
dp[T][j] += dp[i][k];
}
}
}
}
int cur = 0;
for(int i = 0; i < n; i++){
cur += dp[(1 << n) - 1][i];
}
cout << cur;
}
