Problems
Beautiful row
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.
Input data
The first line contains integer n (2 ≤ n ≤ 20). The next line contains n non-negative integers not exceeding 10^9
each.
Output data
Output the number of ways the all given numbers can be placed in a beautiful row.
Examples
Input example #1
3 5 1 6
Output example #1
2