11839번 - Beautiful row 다국어

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 10⁹ each.

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

In the sample 5 = 12₃ and 1 = 1₃, 5 = 101₂ and 6 = 110₂, thus rows 1 5 6 and 6 5 1 are beautiful.