#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
int dp[1100000][20];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int n;
cin >> n;
int a[n];
memset(dp, 0, sizeof(dp));
vector <int> bin(n), tri(n);
for (int i = 0;i < n;i++) {
cin >> a[i];
dp[0][i] = 1;
bin[i] = __builtin_popcount(a[i]);
while (a[i] > 0) {
if (a[i] % 3 == 1) {
tri[i]++;
}
a[i] /= 3;
}
}
int zer[n] = {0};
for (int i = 0;i < n;i++) {
zer[i] = (1 << i);
}
int m = (1 << n);
for (int mask = 1;mask < m;mask++) {
for (int j = 0;j < n;j++) {
if ((zer[j] & mask) == 0) continue;
for (int k = 0;k < n;k++) {
if ((zer[k] & mask) == 0) continue;
if (dp[mask - zer[j]][k] == false) continue;
if (bin[k] == bin[j] || tri[k] == tri[j]) {
dp[mask][j] += dp[mask - zer[j]][k];
}
}
}
}
int pos = 0;
for (int i = 0;i < n;i++) {
pos += dp[m - 1][i];
}
cout << pos;
}
