#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 42
#endif
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> b(n), t(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]++;
}
a[i] /= 3;
}
}
auto is = [&](int i, int j) {
return (b[i] == b[j] || b[i] == t[j] || t[i] == t[j] || t[i] == b[j]);
};
vector<vector<int>> dp(1 << n, vector<int>(n));
for (int s = 1; s < (1 << n); s++) {
if (__builtin_popcount(s) == 1) {
dp[s][__lg(s)] = 1;
}
for (int i = 0; i < n; i++) {
if (s & (1 << i)) continue;
int x = s | (1 << i);
for (int j = 0; j < n; j++) {
if ((s & (1 << j)) && is(i, j)) {
dp[x][i] += dp[s][j];
}
}
}
}
int res = 0;
for (int i = 0; i < n; i++) {
res += dp[(1 << n) - 1][i];
}
cout << res << '\n';
return 0;
}
