#include<bits/stdc++.h> using namespace std; const int N = 20 , LOG = 30; int n; vector<int> a(N); vector<vector<long long>> dp(N , vector<long long>(1 << N)); vector<vector<int>> v(N); int t_o_c(int x){ int cnt = 0; while(x > 0){ cnt += (x % 3 == 1); x /= 3; } return cnt; } int main(){ cin >> n; for(int i = 0;i < n;i ++){ cin >> a[i]; } for(int x = 0;x < n;x ++){ for(int y = 0;y < n;y ++){ if(x != y && (__builtin_popcount(a[x]) == __builtin_popcount(a[y]) || t_o_c(a[x]) == t_o_c(a[y]))){ v[x].push_back(y); } } dp[x][1 << x] = 1LL; } for(int mask = 0;mask < (1 << n);mask ++){ for(int x = 0;x < n;x ++){ if(mask >> x & 1){ for(int y : v[x]){ if(mask >> y & 1){ dp[x][mask] += dp[y][mask ^ (1 << x)]; } } } } } long long ans = 0; for(int i = 0;i < n;i ++){ ans += dp[i][(1 << n) - 1]; } cout << ans << endl; }