#include <bits/stdc++.h> #pragma GCC optimize ("Ofast") #pragma GCC target ("popcnt") using namespace std; bool ok[20][20]; long long dp[20][1<<20]; int arr[20],n; int get1(int x) { int cnt=0; x=arr[x]; while (x){ cnt+=(x%3==1); x/=3; } return cnt; } int get2(int x) {x=arr[x]; return __builtin_popcount(x); } long long ans (int pos, int mask) { long long &ret=dp[pos][mask]; if (ret !=-1) return ret; if(mask==0) return ret=1; ret=0; for (int j=0;j<n;j++){ if ((mask&(1<<j))&&ok[pos][j]) ret+=ans(j,mask^(1<<j)); } return ret; } int main () { memset(dp,-1,sizeof(dp)); cin>>n; for(int i=0;i<n;i++)cin>>arr[i]; for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){ if(get1(i)==get1(j)||get2(i)==get2(j)) { ok[i][j]=ok[j][i]=1; } } long long sum=0; for(int i=0;i<n;i++)sum+=ans(i,(1<<n)-1-(1<<i)); cout<<sum; }