#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;
const int MAX_N = 20;
bool good[MAX_N][MAX_N];
int a[MAX_N];
ll dp[1 << MAX_N][MAX_N];
int get (int x, int k) {
int cnt = 0;
while (x) {
if (x % k == 1)
cnt++;
x /= k;
}
return cnt;
}
bool check (int x, int y) {
return (get (x, 3) == get (y, 3)) || (get (x, 2) == get (y, 2));
}
int main () {
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
good[i][j] = check (a[i], a[j]);
for (int mask = 0; mask < (1 << n); mask++) {
if (mask == 0) {
for (int j = 0; j < n; j++)
dp[1 << j][j] = 1;
}
else {
for (int j = 0; j < n; j++)
if (mask & (1 << j))
for (int k = 0; k < n; k++)
if (not (mask & (1 << k)) && good[j][k])
dp[mask ^ (1 << k)][k] += dp[mask][j];
}
}
ll ans = 0;
for (int i = 0; i < n; i++)
ans += dp[(1 << n) - 1][i];
cout << ans << "\n";
return 0;
}
