#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
int count_bin(int x){
int cnt = 0;
while(x){
if(x & 1) cnt++;
x >>= 1;
}
return cnt;
}
int count_tern(int x){
int cnt = 0;
while(x){
if(x % 3 == 1)
cnt++;
x /= 3;
}
return cnt;
}
ll dp[(1 << 20)][20];
void solve(){
int n; cin >> n;
bool good[n + 1][n + 1];
int a[n + 1];
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
good[i][j] = false;
if(count_bin(a[i]) == count_bin(a[j])) good[i][j] = true;
if(count_tern(a[i]) == count_tern(a[j])) good[i][j] = true;
}
}
for(int i = 0; i < n; i++){
dp[(1 << i)][i] = 1;
}
for(int i = 1; i < (1 << n); i++){
if(__builtin_popcount(i) == 1) continue;
for(int j = 0; j < n; j++){
if(!(i & (1 << j))) continue;
for(int k = 0; k < n; k++){
if(!(i & (1 <<k))) continue;
if(j == k) continue;
if(good[j + 1][k + 1])dp[i][j] += dp[i ^ (1 << j)][k];
}
}
}
ll ans = 0;
for(int j = 0; j < n; j++){
ans += dp[(1 << n) - 1][j];
}
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int test =1 ; //cin >> test;
while(test--){
solve();
}
return 0;
}
