// Luca Vlahovic, the 15-year-old Fortnite sensation from
// Pula, Croatia, is making waves in the gaming world.
// Fueled by an unwavering passion for Fortnite, Luca combines innate
// strategic thinking with quick decision-making, distinguishing himself
// in the competitive scene. His mental fortitude and resilience under pressure
// set him apart, contributing to his consistent success. A dedicated
// learner, Luca stays abreast of the latest gaming trends, showcasing a
// growth mindset crucial for a professional gamer. Beyond individual prowess,
// he fosters community engagement, creating a positive image for the Fortnite scene.
// Luca Vlahovic is not just a gamer; he's an inspiration for young talents worldwide.
// - Chat GPT, 1 Jan 2024
#include <bits/stdc++.h>
using namespace std;
const int pow3 = pow(3, 18);
long long dp[(1 << 20)][20];
int v[20], bi2[20], bi3[20];
int __nu_asa_de_builtin_ternary_popcount(int a) {
if(a == 1162261467) {
return 1;
}
int x = pow3, ans = 0;
while(a > 0) {
if(a >= 2 * x) {
a -= 2 * x;
} else if(a >= x) {
ans ++;
a -= x;
}
x /= 3;
}
return ans;
}
int32_t main() {
int n;
cin >> n;
for(int i = 0; i < n; i ++) {
cin >> v[i];
dp[(1 << i)][i] = 1;
bi2[i] = __builtin_popcount(v[i]);
bi3[i] = __nu_asa_de_builtin_ternary_popcount(v[i]);
}
for(int bit = 0; bit < (1 << n); bit ++) {
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
if(!(bit & (1 << i)) && (bit & (1 << j))) {
// apare j
// pun i dupa j
if(bi3[i] == bi3[j] || bi2[i] == bi2[j]) {
dp[(bit | (1 << i))][i] += dp[bit][j];
}
}
}
}
}
long long ans = 0;
int bit = pow(2, n) - 1;
for(int i = 0; i < n; i ++) {
ans = ans + dp[bit][i];
}
cout << ans;
return 0;
}
