[AHOI2018初中组]球球的排列

题目描述

小可可是一个有着特殊爱好的人。他特别喜欢收集各种各样的球球,至今已经收集了$n$ 个球球。 小可可又是一个有着特殊想法的人。他将他的所有球球从 1 到$n$ 编号,并每天都把球球排成一个全新的排列。 小可可又是一个有着特殊情怀的人。他将每个球球的特点用$a[i]$来表示(注意这里不同的球$a[i]$可能相同)。 小可可又是一个爱恨分明的人。他十分讨厌平方数,所以他规定:一个排列$p$,对于所有的$1 ≤ 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

4
2 2 3 4

输出样例 #1

12

输入样例 #2

9
2 4 8 9 12 4 3 6 11

输出样例 #2

99360

说明

【样例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≤n≤300$,$1≤a[i]≤10^9$。 本题共10 个测试点,编号为1~10,每个测试点额外保证如下: 测试点编号| n的范围|a[i]的范围 -|-|- 1~2|$n≤10$|$a[i]≤10^9$ 3~5|$n≤300$|$1≤a[i]≤2$ 6~8|-|$a[i]≤10^9$且都是质数 9~10|-|$a[i]≤10^9$