#include <bits/stdc++.h>
using namespace std;
long long n, m, a[25], dp[1<<21][25], ans, cnt[25], cnt1[25];
int main (){
cin >> n;
for (int i = 0;i < n;i++) {
cin >> a[i];
cnt[i] = __builtin_popcount(a[i]);
m = a[i];
while (m){
if (m % 3 == 1) cnt1[i]++;
m /= 3;
}
}
for (int i = 0;i < n;i++) dp[1 << i][i] = 1;
for (int i = 0;i < (1 << n);i++)
for (int j = 0;j < n;j++)
for (int o = 0;o < n;o++)
if (!(i & 1<<o) && (cnt[j] == cnt[o] || cnt1[j] == cnt1[o]))
dp[i|(1<<o)][o] += dp[i][j];
for (int i = 0;i < n;i++) ans += dp[(1<<n) - 1][i];
cout << ans;
}
