#include <bits/stdc++.h>
using namespace std;
/* higher types */
typedef int64_t ll;
typedef long double ld;
/* pairs */
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
/* vectors */
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
/* loops */
#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
/* shortforms */
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
/* constants */
const ll infl = numeric_limits<int64_t>::max();
const int infi = numeric_limits<int>::max();
const int modi = 1e9 + 7;
const ll modl = 1e9 + 7;
ll three(ll x)
{
ll ans = 0;
while(x > 0)
{
if(x%3 == 1)
++ans;
x /= 3;
}
return ans;
}
void solve()
{
ll n;
cin >> n;
vl a(n), tw(n), th(n);
fur(i, 0, n-1)
{
cin >> a[i];
tw[i] = __builtin_popcountll(a[i]);
th[i] = three(a[i]);
}
bool adj[n][n];
fur(i, 0, n-1)
fur(j, 0, n-1)
adj[i][j] = (tw[i] == tw[j] || th[i] == th[j]);
vector<vl> dp((1 << n), vl(n, 0));
fur(i, 0, n - 1)
dp[1 << i][i] = 1;
fur(i, 1, (1 << n) - 1)
{
fur(j, 0, n - 1)
{
if(!(i&(1<<j)))
continue;
fur(k, 0, n - 1)
{
if(k == j || !(i & (1 << k)) || !adj[k][j])
continue;
dp[i][j] += dp[i - (1 << j)][k];
}
}
}
ll ans = 0;
fur(i, 0, n - 1)
ans += dp[(1 << n) - 1][i];
cout << ans << nl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
ll t = 1;
// cin >> t;
while(t--)
{
solve();
}
}
