#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 1e9;
const int MOD = 1e9 + 7;
int n, v[20], ok[20][20];
short bits[(1 << 20)][20];
long long dp[(1 << 20)][20];
int base2 (int x) {
int cnt = 0;
while (x) {
if (x % 2 == 1)
cnt++;
x /= 2;
}
return cnt;
}
int base3 (int x) {
int cnt = 0;
while (x) {
if (x % 3 == 1)
cnt++;
x /= 3;
}
return cnt;
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> v[i];
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (base2(v[i]) == base2(v[j]) || base3(v[i]) == base3(v[j]))
ok[i][j] = 1;
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++)
if (i & (1 << j))
bits[i][++bits[i][0]] = j;
}
for (int i = 1; i < (1 << n); i++) {
if (bits[i][0] == 1) {
dp[i][bits[i][1]] = 1;
continue;
}
for (int j = 1; j <= bits[i][0]; j++)
for (int k = 1; k <= bits[i][0]; k++)
if (j != k) {
int b1 = bits[i][j];
int b2 = bits[i][k];
if (ok[b1][b2])
dp[i][b1] = (dp[i ^ (1 << b1)][b2] + dp[i][b1]);
}
}
long long ans = 0;
for (int i = 0; i < n; i++)
ans += dp[(1 << n) - 1][i];
cout << ans;
return 0;
}
