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

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

Output

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