아름다운 줄

알리아미르가 정수 $N$개를 한 줄로 늘어놓았다. 이웃한 두 수가 언제나 이진법에서 1의 개수가 같거나 삼진법에서 1의 개수가 같으면, 그 줄을 아름다운 줄이라고 한다.

이진법에서 1의 개수는 그 수를 2진수로 적었을 때 숫자 1인 자리의 개수이고, 삼진법에서 1의 개수는 3진수로 적었을 때 숫자 1인 자리의 개수이다. 예를 들어 $5$는 2진수로 $101$이라 1이 두 개이고, 3진수로 $12$라 1이 한 개이다. $0$은 두 진법 모두 1의 개수가 $0$이다.

주어진 수를 모두 사용해 만들 수 있는 아름다운 줄이 몇 가지인지 세어라. 같은 값이 여러 번 주어지기도 하며, 늘어놓은 결과가 수열로서 같으면 한 가지로 센다.

첫째 줄에 정수 $N$이 주어진다. ($2 \le N \le 20$)

둘째 줄에 정수 $N$개가 공백으로 구분되어 주어진다. 각 수는 $0$ 이상 $10^9$ 이하이다.

주어진 수를 모두 늘어놓아 만들 수 있는 아름다운 줄의 개수를 한 줄에 출력한다. 답은 최대 $20!$이라 64비트 정수 범위에 들어간다.

첫 번째 예제에서 $5$는 3진수로 $12$, $1$은 3진수로 $1$이라 1의 개수가 같다. 또 $5$는 2진수로 $101$, $6$은 2진수로 $110$이라 1의 개수가 같다. 그래서 아름다운 줄은 1 5 6과 6 5 1 두 가지이다.