On the Bench

给定一个序列 $a(a_i\le 10^9)$，长度为 $n(n\le 300)$。 试求有多少 $1$ 到 $n$ 的排列 $p_i$，满足对于任意的 $2\le i\le n$ 有 $a_{p_{i-1}}\times a_{p_i}$ 不为完全平方数，答案对 $10^9+7$ 取模。

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<=i&lt;n $ condition, that $ a_{pi}·a_{pi+1} $ is not perfect square, holds. Leha wants to find number of right permutations modulo $ 10^{9}+7 $ .

First line of input data contains single integer $ n $ ( $ 1<=n<=300 $ ) — length of the array. Next line contains $ n $ integers $ a_{1},a_{2},...\ ,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ) — found array.

Output single integer — number of right permutations modulo $ 10^{9}+7 $ .

3
1 2 4

2

7
5 2 4 2 4 1 1

144

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.