아름다운 줄

시간 제한3초메모리 제한256 MB

요약

주어진 수를 모두 나열할 때 이웃한 두 수가 이진수나 삼진수에서 1 개수가 같은 서로 다른 행 개수를 셉니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그래프, 조합론
정답자: 아직 제출이 없습니다

문제

알리아미르가 정수 $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 두 가지이다.

예제3

예제 1
입력
```
3
5 1 6
```
예상 출력
```
2
```
예제 2
입력
```
2
3 4
```
예상 출력
```
0
```
예제 3
입력
```
2
7 7
```
예상 출력
```
1
```