#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
int cnt2(int n)
{
int ans = 0;
while(n)
{
ans+=(n%2==1);
n/=2;
}
return ans;
}
int cnt3(int n)
{
int ans = 0;
while(n)
{
ans+=(n%3==1);
n/=3;
}
return ans;
}
int dp[20][1ll<<20];
signed main()
{
fast();
int n;
cin >> n;
vector<vector<int>> adj(n);
vector<in> a(n);
for(int i = 0; i < n; i++)
{
int x;
cin >> x;
a[i] = {cnt2(x), cnt3(x)};
for(int j = 0; j < i; j++)
{
if(a[i].f == a[j].f || a[i].s == a[j].s)
{
adj[i].pb(j);
adj[j].pb(i);
}
}
}
int ans = 0;
for(int j = 1; j < (1ll<<n); j++)
{
for(int i = 0; i < n; i++)
{
if((j^(1ll<<i)) > j)
continue;
int k = j^(1ll<<i);
if(k==0)
{
dp[i][j] = 1;
continue;
}
dp[i][j] = 0;
for(int v: adj[i])
{
if((k^(1ll<<v)) > k)
continue;
dp[i][j]+=dp[v][k];
}
}
}
for(int i = 0; i < n; i++)
ans+=dp[i][(1ll<<n)-1];
cout << ans;
return 0;
}
