#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44
using namespace std;
const int MAXN = 20;
ll dp[1 << MAXN][MAXN];
int cnt2[MAXN], cnt3[MAXN];
inline int get2(int x) {
return __builtin_popcount(x);
}
inline int get3(int x) {
int cnt = 0;
while(x > 0) {
cnt += ((x % 3) == 1);
x /= 3;
}
return cnt;
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for(i = 0; i < n; i++) {
int x;
cin >> x;
cnt2[i] = get2(x);
cnt3[i] = get3(x);
}
for(int conf = 1; conf < (1 << n); conf++) {
if((conf & (conf - 1)) == 0) {
int bit = 0;
while((conf & (1 << bit)) == 0) {
bit++;
}
dp[conf][bit] = 1;
}
else {
vector <int> cur;
for(int bit = 0; bit < n; bit++) {
if(conf & (1 << bit)) {
cur.push_back(bit);
}
}
int sz = cur.size();
for(int a = 0; a < sz; a++) {
for(int b = 0; b < sz; b++) {
if(a != b && (cnt2[cur[a]] == cnt2[cur[b]] || cnt3[cur[a]] == cnt3[cur[b]])) {
dp[conf][cur[a]] += dp[conf ^ (1 << cur[a])][cur[b]];
}
}
}
}
}
ll ans = 0;
for(i = 0; i < n; i++) {
ans += dp[(1 << n) - 1][i];
}
cout << ans;
//cin.close();
//cout.close();
return 0;
}
