#include <bits/stdc++.h>
// author : aykhn
using namespace std;
typedef long long ll;
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcount
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define int ll
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F
const int MXN = 20;
int n;
int a[MXN];
pii cnt[MXN];
int dp[(1 << MXN)][MXN];
signed main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
for (int j = 0; j <= 30; j++)
{
cnt[i].fi += a[i] >> j & 1;
}
int pw = 387420489;
int y = a[i];
while (pw)
{
int x = y/pw;
cnt[i].se += (x == 1);
y -= x * pw;
pw /= 3;
}
}
for (int i = 0; i < n; i++) dp[(1 << i)][i] = 1;
for (int mask = 0; mask < (1 << n); mask++)
{
if (bpc(mask) <= 1) continue;
for (int i = 0; i < n; i++)
{
if (!(mask >> i & 1)) continue;
for (int j = 0; j < n; j++)
{
if (!(mask >> j & 1)) continue;
if (cnt[i].fi == cnt[j].fi || cnt[i].se == cnt[j].se) dp[mask][i] += dp[(mask ^ (1 << i))][j];
}
}
}
int res = 0;
for (int i = 0; i < n; i++) res += dp[(1 << n) - 1][i];
cout << res << '\n';
}
