P4448 [AHOI2018初中组] 球球的排列
题目描述
小可可是一个有着特殊爱好的人。他特别喜欢收集各种各样的球球，至今已经收集了 $n$ 个球球。
小可可又是一个有着特殊想法的人。他将他的所有球球从 $1$ 到 $n$ 编号，并每天都把球球排成一个全新的排列。
小可可又是一个有着特殊情怀的人。他将每个球球的特点用 $a_i$ 来表示（注意这里不同的球 $a_i$ 可能相同）。
小可可又是一个爱恨分明的人。他十分讨厌平方数，所以他规定：一个排列 $p$，对于所有的 $1 \le i < n$，$a_{p_i}\times a_{p_{i+1}}$ 不是一个平方数，这样的排列 $p$ 才是合法的。
小可可一直坚持每天排一个全新的合法的排列。有一天，他心血来潮，想知道所有合法排列的个数。小可可十分强，他当然知道怎么算。不过，他想用这个题来考考身在考场的你。这个数可能太大了，所以你只需要告诉小可可合法排列个数对 $10^9+7$ 取模的结果就可以了。
你能正确回答小可可的问题吗？如果能的话，他说不定会送个球球给你呢……
输入格式
输入有两行：
第一行一个正整数 $n$，表示小可可拥有的球球个数。
第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示编号为 $i$ 的球球的特点。
输出格式
输出一行，包括一个正整数，表示合法排列个数对 $10^9+7$（即 $1000000007$）取模的结果。
说明/提示
【样例 $1$ 解释】
$12$ 种合法的排列分别为：
```
1,3,2,4
2,3,1,4
3,1,4,2
3,2,4,1
1,3,4,2
2,3,4,1
1,4,2,3
2,4,1,3
4,1,3,2
4,2,3,1
1,4,3,2
2,4,3,1
```
【数据范围】
对于 $100\%$ 的数据满足：$1\le n\le 300$，$1 \le a_i \le 10^9$。
本题共 $10$ 个测试点，编号为 $1 \sim 10$，每个测试点额外保证如下：
测试点编号| $n$ 的范围|$a_i$ 的范围
-|-|-
$1 \sim 2$|$n\le 10$|$a_i\le 10^9$
$3 \sim 5$|$n\le 300$|$a_i\le 2$
$6 \sim 8$|$n\le 300$|$a_i\le 10^9$ 且 $a_i$ 是质数
$9 \sim 10$|$n\le 300$|$a_i\le 10^9$