#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
const int N_ = 20;
int N, A[N_];
bool G[N_][N_];
int B[N_], C[N_];
ll Table[N_][1<<N_];
int main() {
int i, j, k;
scanf("%d", &N);
for(i = 0; i < N; i++) scanf("%d", A+i);
for(i = 0; i < N; i++) {
for(j = A[i]; j > 0; j /= 2) if(j % 2 == 1) ++B[i];
for(j = A[i]; j > 0; j /= 3) if(j % 3 == 1) ++C[i];
}
for(i = 0; i < N; i++) for(j = i+1; j < N; j++)
G[i][j] = G[j][i] = (B[i] == B[j] || C[i] == C[j]);
for(i = 0; i < N; i++) Table[i][1<<i] = 1;
for(int state = 1; state < (1<<N); state++) {
for(i = 0; i < N; i++) if(state & (1<<i)) {
int prev = state ^ (1<<i);
for(j = 0; j < N; j++) if((prev & (1<<j)) && G[j][i]) Table[i][state] += Table[j][prev];
}
}
ll res = 0;
for(i = 0; i < N; i++) res += Table[i][(1<<N)-1];
printf("%lld\n", res);
return 0;
}
