시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 1 1 1 100.000%

문제

Ali-Amir wrote N numbers in a row. A row is called beautiful if any two of the neighbour numbers in the row have got the same amount of ones in binary or ternary notations.

Ali-Amir wants to count the number of ways the all given numbers can be written in a beautiful row.

입력

The first line of input file contains integer N (2 ≤ N ≤ 20). The next line contains N non-negative integers not exceeding 109 each.

출력

Output the number of ways the all given numbers can be placed in a beautiful row.

예제 입력

3
5 1 6

예제 출력

2

힌트

In the sample 5 = 123 and 1 = 13, 5 = 1012 and 6 = 1102, thus rows 1 5 6 and 6 5 1 are beautiful.