A year ago on the bench in public park Leha found an array of n numbers. Leha believes that permutation p is right if for all 1 \le i \lt n condition, that api \cdot api+1 is not perfect square, holds. Leha wants to find number of right permutations modulo 109+7.

First line of input data contains single integer n (1 \le n \le 300) - length of the array.

Next line contains n integers a1,a2,... ,an (1 \le ai \le 109) - found array.

Output single integer - number of right permutations modulo 109+7.

For first example:

[1,2,4] - right permutation, because 2 and 8 are not perfect squares.

[1,4,2] - wrong permutation, because 4 is square of 2.

[2,1,4] - wrong permutation, because 4 is square of 2.

[2,4,1] - wrong permutation, because 4 is square of 2.

[4,1,2] - wrong permutation, because 4 is square of 2.

[4,2,1] - right permutation, because 8 and 2 are not perfect squares.