#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define nn "\n"
#define x_x ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define intt int _; cin >> _; while (_--)
#define emp push_back
#define mod 1000000007
#define all(v) v.begin(), v.end()
#define ld long double
#define A first
#define B second
//#define int long long
typedef long long ll;
const ld eps = 1e-27;
// diff between decimals 0.000000001 mt19937 mt(time(nullptr));
ll dp[(1<<20)][20];
int main() {
x_x
int n; cin>>n; pair<int,int> ar[n];
for (int i=0; i<n; i++) {
int x,y; cin>>x; int c=0;
y=x; while (y) {c+=(y%2); y/=2;}
ar[i].A=c; c=0;
y=x; while (y) {c+=(y%3==1); y/=3;}
ar[i].B=c;
dp[(1<<i)][i]=1;
}
ll to=(1<<n);
for (int msk=1; msk<to; msk++) {
for(int ind=0; ind<n; ind++) {
if (!(msk&(1<<ind))) continue;
int msk2=(msk^(1<<ind));
ll x=0;
for (int j=0; j<n; j++) {
if (!(msk2&(1<<j))) continue;
if (ar[ind].A==ar[j].A||ar[ind].B==ar[j].B)
x+=dp[msk2][j];
}
dp[msk][ind]+=x;
}
}
--to; ll ans=0;
for (int i=0; i<n; i++)
ans+=dp[to][i];
cout<<ans;
return 0;
}
