#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "
#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb push_back
ll get(int x, int y) {
ll res = 0;
while(x) {
res += (x % y == 1);
x /= y;
}
return res;
}
void solve()
{
int n;
cin >> n;
vi a(n);
for(auto &i : a) {
cin >> i;
}
bool spec[n][n] = {};
FOR(i, 0, n) {
FOR(j, 0, n) {
spec[i][j] = (get(a[i], 2) == get(a[j], 2) || get(a[i], 3) == get(a[j], 3));
}
}
ll dp[(1<<n)][n] = {};
FOR(s, 0, (1<<n)) {
FOR(i, 0, n) {
ll curr = (1<<i);
if((curr & s) == 0)
continue;
ll last = s ^ curr;
if(last == 0) {
dp[s][i] = 1;
continue;
}
FOR(j, 0, n) {
if(i == j)
continue;
if(!spec[i][j])
continue;
dp[s][i] += dp[last][j];
}
}
}
ll ans = 0;
FOR(i, 0, n) {
ans += dp[(1 << n) - 1][i];
}
cout << ans << nl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
// cin >> t;
while (t--)
{
solve();
}
}
