#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 22
int n, a[N], b3[N];
ll ans, dp[N][1<<N][2];
inline int beautiful(int i, int j) { return (__builtin_popcount(a[i]) == __builtin_popcount(a[j])) || b3[i] == b3[j]; }
int main()
{
ShinLena;
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> a[i];
for (int x = a[i]; x; b3[i] += (x % 3) == 1, x /= 3);
dp[i][1<<i][1] = 1;
}
for (int k = 0; k < (1 << n); ++k)
{
for (int j = 0; j < n; ++j)
{
if (!(k&(1<<j))) continue;
if (dp[j][k][0]) continue;
for (int l = 0; l < n; ++l)
{
if (k & (1 << l))
{
if (beautiful(j, l)) dp[j][k][1] += dp[l][k&~(1<<j)][1];
else dp[j][k][0] += dp[l][k&~(1<<j)][1];
}
}
}
}
for (int i = 0; i < n; ++i) ans += dp[i][(1<<n)-1][1];
cout << ans;
return 0;
}
