#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)
#define bit(x, y) (((x) >> (y)) & (1ll))
using namespace std;
typedef long long ll;
const int N = 21;
int n, a[N], b2[N], b3[N];
ll f[20][1ll << 20];
ll calc(int i, int s){
if(f[i][s] != -1) return f[i][s];
if(s==(1ll << (n)) - 1){
f[i][s] = 1;
return 1;
}
ll ans = 0;
for(int j = 0; j < n; j++){
if(bit(s, j)) continue;
if(b2[i + 1] != b2[j + 1] && b3[i + 1] != b3[j + 1]) continue;
ans = ans + calc(j, s + (1ll << j));
}
f[i][s] = ans;
return ans;
}
int main(){
ios_base::sync_with_stdio(0);
cin >> n;
f1(i, n){
cin >> a[i];
b2[i] = __builtin_popcount(a[i]);
while(a[i]){
int x = a[i]%3;
b3[i] += (x==1);
a[i] /= 3;
}
}
memset(f, -1, sizeof(f));
ll ans = 0;
f1(i, n) ans = ans + calc(i - 1, (1ll << (i - 1)));
cout << ans;
}
