import java.util.*;
import java.io.*;
public class beauty {
static long[] a = new long[100];
static long[] b = new long[100];
static long[][] dp = new long[1 << 20][23];
static int n;
static long rec(long mask, int last) {
if (mask == (pow(n) - 1)) return 1;
if (last != -1 && dp[(int) mask][last] != -1) return dp[(int) mask][last];
long an = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) == 0) {
if (last == -1 || a[(int) last] == a[i] || b[(int) last] == b[i]) {
an += rec(mask | pow(i), i);
}
}
}
if(last != -1)dp[(int) mask][last] = an;
return an;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int i;
long ans = 0;
n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for (i = 0; i < n; i++) {
long p = Integer.parseInt(st.nextToken());
a[i] = Long.bitCount(p);
long p1 = p;
while (p1 > 0) {
if (p1 % 3 == 1) b[i]++;
p1 /= 3;
}
}
for (i = 0; i < pow(20); i++) {
Arrays.fill(dp[i], -1);
}
ans += rec(0, -1);
PrintWriter pw = new PrintWriter(System.out);
pw.println(ans);
pw.close();
}
public static long pow(int i) {
long ans = 1;
while(i > 0) {
ans *= 2;
i--;
}
return ans;
}
}
