#include <bits/stdc++.h>
using namespace std;
void solve() {
int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; i++) {
cin >> a[i];
}
vector adj(N, vector<int>{});
auto nums = [&] (int x, int k) -> int {
int ans = 0;
while (x > 0) {
ans += (x % k == 1);
x /= k;
}
return ans;
};
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (nums(a[i], 2) == nums(a[j], 2) || nums(a[i], 3) == nums(a[j], 3)) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
vector dp(N, vector<long long>( (1 << N) ));
long long ans = 0;
for (int mask = 0; mask < (1 << N); mask++) {
for (int last = 0; last < N; last++) {
if (mask & (1 << last)) {
if ( (mask ^ (1 << last)) == 0) {
dp[last][mask] = 1;
continue;
}
for (int j : adj[last]) {
dp[last][mask] += dp[j][ mask ^ (1 << last) ];
}
}
}
}
for (int j = 0; j < N; j++) ans += dp[j][ (1 << N) - 1 ];
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests = 1;
// cin >> tests;
while (tests--) solve();
return 0;
}
/*
if we are going to apply operation to a height a[i], it's optimal to remove the rightmost instance
*/
