#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
vector<vector<ll>> dp(1 << 20, vector<ll>(n, 0));
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> bin(n), ter(n);
for (int i = 0; i < n; ++i) {
bin[i] = __builtin_popcount(a[i]);
int n = a[i];
while (n > 0) {
if (n % 3 == 1) ++ter[i];
n /= 3;
}
}
for (int i = 0; i < n; ++i) dp[1 << i][i] = 1;
for (int mask = 0; mask < (1 << n); ++mask) {
if (__builtin_popcount(mask) == 1) continue;
for (int b = 0; b < n; ++b) {
if (mask & (1 << b)) {
for (int b2 = 0; b2 < n; b2++) {
if (!(mask & (1 << b2))) continue;
if (b2 != b && (bin[b] == bin[b2] || ter[b] == ter[b2])) dp[mask][b] += dp[mask - (1 << b)][b2];
}
}
}
}
ll ans = 0;
for (int b = 0; b < n; ++b) {
ans += dp[(1 << n) - 1][b];
}
cout << ans << endl;
return 0;
}
