#include <bits/stdc++.h>
using namespace std;
int main()
{
long long N;
cin >> N;
vector<long long> Tab(N);
for (long long i = 0; i < N; i++)
{
cin >> Tab[i];
}
vector<long long> Bin(N), Ter(N);
for (long long i = 0; i < N; i++)
{
long long x = Tab[i];
while (x)
{
Bin[i] += x % 2;
x /= 2;
}
x = Tab[i];
while (x)
{
if (x % 3 == 1)
Ter[i]++;
x /= 3;
}
}
vector<vector<long long>> dp(N, vector<long long>(1 << N));
for (long long i = 0; i < N; i++)
dp[i][(1 << i)] = 1;
for (long long i = 0; i < (1 << N); i++)
{
for (long long j = 0; j < N; j++)
{
if (dp[j][i] == 0)
continue;
for (long long k = 0; k < N; k++)
{
if (i & (1 << k))
continue;
if (Bin[j] == Bin[k] || Ter[j] == Ter[k])
dp[k][i | (1 << k)] += dp[j][i];
}
}
}
long long tot = 0;
for (long long i = 0; i < N; i++)
{
tot += dp[i][(1 << N) - 1];
}
cout << tot;
}
