#include <bits/stdc++.h>
using namespace std;
#define int long long
#define A first
#define B second
int n , a[20] , dp[20][1<<20] , co[20][20];
int fact(int i , int b){
int x = a[i];
int ans =0 ;
while(x > 0){
if (x%b == 1) ans++;
x/=b;
}
return ans;
}
void pre(){
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < i ; j++){
int a = fact(i ,2), b = fact(i , 3) , c = fact(j ,2 ) , d= fact(j , 3);
if (a == c || b == d) { co[i][j] = 1; co[j][i] = 1;}
}
}
}
// int brute(int last , int mask , set<int> &st){
// if ( mask == (1<<n) - 1) return 1;
// if (~dp[last][mask]) return dp[last][mask];
// int ans = 0 ;
// for (auto i = st.begin() ; i!=st.end() ; i++){
// if (!(mask & (1<<*i))){
// if (mask == 0 || co[last][*i]) {
// set<int> b = st;
// b.erase(*i);
// ans += brute(*i , (mask | 1<<*i) , b);
// }
// }
// }
// return dp[last][mask] = ans;
// }
void brute(){
for (int mask = (1<<n) - 1 ; mask >= 0 ; mask--){
for (int last = n-1 ; last >= 0 ; last--){
if (mask == (1<<n) - 1) { dp[last][mask] = 1; continue; }
for (int i = 0 ; i < n ; i++) {
if (!(mask & (1<<i))){
if (mask == 0 || co[last][i]){
dp[last][mask] += dp[i][mask | (1<<i)];
}
}
}
}
}
cout << dp[0][0];
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 0 ; i < n ; i++) cin >> a[i];
pre();
brute();
}
