#include <bits/stdc++.h>
using namespace std ;
const int MAX = 20 ;
int arr[MAX] ;
int n ;
int cnt2[MAX] , cnt3[MAX] ;
int calc(int x)
{
int cnt = 0 ;
while(x > 0)
{
cnt += (x%3 == 1) ;
x /= 3 ;
}
return cnt ;
}
long long dp[MAX][(1 << MAX)] ;
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 0 ; i < n ; ++i)
cin>>arr[i] ;
for(int i = 0 ; i < n ; ++i)
cnt2[i] = __builtin_popcount(arr[i]) , cnt3[i] = calc(arr[i]) ;
for(int i = 0 ; i < n ; ++i)
dp[i][(1 << i)] = 1 ;
for(int mask = 0 ; mask < (1 << n) ; ++mask)
{
for(int i = 0 ; i < n ; ++i)
{
if((!(mask & (1 << i))))
continue ;
for(int j = 0 ; j < n ; ++j)
{
if((!(mask & (1 << j))))
continue ;
if(cnt2[i] == cnt2[j] || cnt3[i] == cnt3[j])
dp[i][mask] += dp[j][mask ^ (1 << i)] ;
}
}
}
long long ans = 0 ;
for(int i = 0 ; i < n ; ++i)
ans += dp[i][(1 << n) - 1] ;
return cout<<ans<<"\n" , 0 ;
}
