#include <bits/stdc++.h>
using namespace std;
int vu = 0, nb[20], n, compteur = 0;
vector<int> graph[20];
int nbOneBin(int a) {
int compteur1 = 0;
for(int loop = 30; loop >= 0; --loop) {
if(a >= (1 << loop)) {
a -= (1 << loop);
compteur1++;
}
}
return compteur1;
}
int nbOneTer(int a) {
int compteur1 = 0;
for(int loop = 18; loop >= 0; --loop) {
if(a >= 2*int(pow(3, loop))) {
a -= 2*int(pow(3, loop));
}
else if(a >= int(pow(3, loop))) {
a -= int(pow(3, loop));
compteur1++;
}
}
return compteur1;
}
void dfs(int pos) {
vu = vu | (1 << pos);
if(vu == (1 << n) - 1) {
compteur++;
}
else {
for(int loop = 0; loop < graph[pos].size(); ++loop) {
if((vu | (1 << graph[pos][loop])) != vu) {
dfs(graph[pos][loop]);
}
}
}
vu -= (1 << pos);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int loop = 0; loop < n; ++loop) {
cin >> nb[loop];
}
for(int loop = 0; loop < n; ++loop) {
for(int looping = loop+1; looping < n; ++looping) {
if(nbOneBin(nb[loop]) == nbOneBin(nb[looping]) || nbOneTer(nb[loop]) == nbOneTer(nb[looping])) {
graph[loop].push_back(looping);
graph[looping].push_back(loop);
}
}
}
for(int loop = 0; loop < n; ++loop) {
dfs(loop);
}
cout << compteur << '\n';
}
