#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
int n, ans = 0;
cin >> n;
vector<int> a(n + 1, 0), c1(n + 1, 0), c2(n + 1, 0);
vector<vector<int>> dp((1 << n) + 10, vector<int>(n + 1, 0));
vector<int> adj[n + 1];
// dp[mask][v] = number of ways to make a sequence with mask elements
// where the last value in the sequence in v
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < n; ++i){
c1[i] = __builtin_popcount(a[i]);
while(a[i]){
if(a[i] % 3 == 1) c2[i] += 1;
a[i] /= 3;
}
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(i ^ j){
if(c1[i] == c1[j] || c2[i] == c2[j]) adj[i].push_back(j);
}
}
}
for(int i = 0; i < n; ++i){
dp[1 << i][i] = 1;
}
for(int mask = 1; mask < (1 << n); ++mask){
for(int j = 0; j < n; ++j){
if(mask & (1 << j)){
for(auto it : adj[j]){
if(mask & (1 << it)){
dp[mask][j] += dp[mask ^ (1 << j)][it];
}
}
}
}
}
for(int i = 0; i < n; ++i){
ans += dp[(1 << n) - 1][i];
}
cout << ans << "\n";
return 0;
}
