Beautiful row

Beautiful row

Input le: b.in

Output le: b.out

Time limit: 3 seconds

Memory limit: 256 megabytes

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 rst line of input le 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.

Examples

In.

3

5 1 6

Out

2

Note

In the sample 5 = 123 and 1 = 13, 5 = 1012 and 6 = 1102, thus rows 1 5 6 and 6 5 1 are beautiful.

In 25% of testcases N  4.

In 50% of testcases N  10.