#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> cnt2(n), cnt3(n);
function<int(int)> calc = [](int x) {
int ret = 0;
while (x) {
ret += (x % 3 == 1);
x /= 3;
}
return ret;
};
for (int i = 0; i < n; i++) {
int a;
cin >> a;
cnt2[i] = __builtin_popcount(a);
cnt3[i] = calc(a);
}
vector<vector<long long>> dp(n, vector<long long>(1 << n));
for (int i = 0; i < n; i++) {
dp[i][1 << i] = 1;
}
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
if (!(mask & (1 << i))) {
continue;
}
for (int j = 0; j < n; j++) {
if (!(mask & (1 << j))) {
continue;
}
if (cnt2[i] == cnt2[j] || cnt3[i] == cnt3[j]) {
dp[i][mask] += dp[j][mask ^ (1 << i)];
}
}
}
}
long long res = 0;
for (int i = 0; i < n; i++) {
res += dp[i][(1 << n) - 1];
}
cout << res;
return 0;
}
