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 contains integer n (2 ≤ n ≤ 20). The next line contains n non-negative integers not exceeding 10^9
each.
Output the number of ways the all given numbers can be placed in a beautiful row.