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.</p>

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.

예제 입력

3
5 1 6

예제 출력

2

힌트

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