#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1048576][20], a[20];
vector<int> adj[20];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, ans=0;
cin >> n;
for (int i=0; i<n; i++)
cin >> a[i];
for (int i=0; i<n; i++)
{
for (int j=i+1; j<n; j++)
{
int cnt2=0, cnt3=0, power=1;
for (int k=0; k<30; k++)
{
if (a[i]&(1<<k))
cnt2++;
if (a[j]&(1<<k))
cnt2--;
}
for (int k=0; k<19; k++)
{
if (a[i]%(power*3)/power==1)
cnt3++;
if (a[j]%(power*3)/power==1)
cnt3--;
power*=3;
}
if (!cnt2 || !cnt3)
{
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
for (int i=1; i<(1<<n); i++)
{
vector<int> vec;
for (int j=0; j<n; j++)
if (i&(1<<j))
vec.push_back(j);
if (vec.size()==1)
{
dp[i][vec[0]]=1;
continue;
}
for (int u:vec)
for (int v:adj[u])
if (i&(1<<v))
dp[i][u]+=dp[i^(1<<u)][v];
}
for (int i=0; i<n; i++)
ans+=dp[(1<<n)-1][i];
cout << ans;
}
