//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ar array
const int mxN=20;
int n, a[mxN];
ll dp[mxN][1<<mxN];
ar<int, 2> cnt[mxN];
ar<int, 2> calc(int x) {
int cnt2=0, cnt3=0;
int p=x;
while(p) {
if(p&1) ++cnt2;
p/=2;
}
p=x;
while(p) {
if(p%3==1) ++cnt3;
p/=3;
}
return {cnt2, cnt3};
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n; ++i) {
cin >> a[i];
cnt[i]=calc(a[i]);
}
ll ans=0;
for(int i=0; i<n; ++i) dp[i][1<<i]=1;
for(int msk=1; msk<(1<<n); ++msk) {
for(int i=0; i<n; ++i) {
if(msk&(1<<i)) {
for(int j=0; j<n; ++j) {
if(i==j) continue;
if(((msk&(1<<j))>0)&&((cnt[i][0]==cnt[j][0])||(cnt[i][1]==cnt[j][1]))) {
dp[i][msk]+=dp[j][msk^(1<<i)];
}
}
}
}
}
int sz=(1<<n)-1;
for(int i=0; i<n; ++i) ans+=dp[i][sz];
cout << ans << "\n";
return 0;
}
