#include <bits/stdc++.h>
using namespace std;
#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
#define type(x) __typeof(x.begin())
#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)
#define pb push_back
#define mp make_pair
#define nd second
#define st first
#define endl '\n'
typedef pair < int ,int > pii;
typedef long long ll;
const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 2e5 + 5;
int F, dp[20][1 << 20], n, m, c[20][20], a[20];
int take2(int x) { int sum = 0; while(x) { sum += x % 2 == 0; x /= 2; } return sum; }
int take3(int x) { int sum = 0; while(x) { sum += x % 3 == 0; x /= 3; } return sum; }
ll f(int node, int mask) {
if(mask == F) return 1;
int &r = dp[node][mask];
if(r != -1) return r;
r = 0;
FOR(i, 0, n)
if(!(mask & (1 << i)) && c[node][i])
r += f(i, mask | (1 << i));
return r;
}
int main() {
scanf("%d",&n); F = (1 << n) - 1; --n;
FOR(i, 0, n)
scanf("%d", &a[i]);
FOR(i, 0, n)
FOR(j, 0, n)
if(i != j && (take2(a[i]) == take2(a[j]) || take3(a[i]) == take3(a[j]))) {
c[i][j] = 1;
}
memset(dp, -1, sizeof dp);
ll ans = 0;
FOR(i, 0, n)
ans += f(i, (1 << i));
cout << ans << endl;
return 0;
}
