#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define el '\n'
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define fi first
#define se second
template <class T1, class T2>
bool minimize(T1 &a, T2 b) {
if(a > b){a = b; return true;} return false;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b) {
if(a < b) {a = b; return true;} return false;
}
const int MOD = 1337377;
template <class T1, class T2>
void add(T1 &a, T2 b) {
a += b;
if(a >= MOD) a -= MOD;
}
const ll INF = (ll)1e18 + 10LL;
const int oo = (int)1e9 + 10;
const int MAX = 250250;
const int LG = 18;
int N, A[MAX], two[MAX], three[MAX];
void init (void) {
cin >> N;
FOR(i, 1, N) {
cin >> A[i];
two[i] = __builtin_popcount(A[i]);
int x = A[i];
while(x > 0) {
if(x % 3 == 1) three[i]++;
x /= 3;
}
}
}
ll f[MASK(21) + 10][22];
void solve (void) {
FOR(i, 0, N) f[MASK(i)][i] = 1;
FOR(mask, 0, MASK(N) - 1) {
for(int i = 0; i < N; i++) if(BIT(mask, i)) {
for(int j = 0; j < N; j++) if(!BIT(mask, j)) {
if(two[i + 1] == two[j + 1] || three[i + 1] == three[j + 1]) {
f[mask | MASK(j)][j] += f[mask][i];
}
}
}
}
ll ans = 0;
FOR(i, 0, N - 1) {
ans += f[MASK(N) - 1][i];
}
cout << ans << el;
}
int main (void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "test"
int ntest = 1;
// cin >> ntest;
// srand(time(0));
while(ntest--) {
init();
solve();
}
return 0;
}
