#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
int C2(int x) {
return __builtin_popcount(x);
}
int C3(int x) {
int cnt = 0;
while (x) {
cnt += x % 3 == 1;
x /= 3;
}
return cnt;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; cin >> n;
vector<int> a(n);
for (int &x : a) {
cin >> x;
}
vector b(n, vector<bool>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
b[i][j] = C2(a[i]) == C2(a[j]) || C3(a[i]) == C3(a[j]);
}
}
vector dp(n, vector<long long>(1 << n, 0));
for (int i = 0; i < n; ++i) {
dp[i][1 << i] = 1;
}
for (int m = 0; m < 1 << n; ++m) {
for (int i = 0; i < n; ++i) {
if (dp[i][m]) {
for (int j = 0; j < n; ++j) {
if (!(m >> j & 1) && b[i][j]) {
dp[j][m + (1 << j)] += dp[i][m];
}
}
}
}
}
long long res = 0;
for (int i = 0; i < n; ++i) {
res += dp[i][(1 << n) - 1];
}
cout << res;
return 0;
}
