#P4448. [AHOI2018初中组] 球球的排列

    ID: 4882 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划,dp2018安徽容斥概率论,统计

[AHOI2018初中组] 球球的排列

题目描述

小可可是一个有着特殊爱好的人。他特别喜欢收集各种各样的球球,至今已经收集了nn 个球球。

小可可又是一个有着特殊想法的人。他将他的所有球球从 1 到nn 编号,并每天都把球球排成一个全新的排列。

小可可又是一个有着特殊情怀的人。他将每个球球的特点用a[i]a[i]来表示(注意这里不同的球a[i]a[i]可能相同)。

小可可又是一个爱恨分明的人。他十分讨厌平方数,所以他规定:一个排列pp,对于所有的1i<n1 ≤ i < na[pi]×a[pi+1]a[p_i]\times a[p_{i+1}] 不是一个平方数,这样的排列pp 才是合法的。

小可可一直坚持每天排一个全新的合法的排列。有一天,他心血来潮,想知道所有合法排列的个数。小可可十分强,他当然知道怎么算。不过,他想用这个题来考考身在考场的你。这个数可能太大了,所以你只需要告诉小可可合法排列个数对109+710^9+7 取模的结果就可以了。

你能正确回答小可可的问题吗?如果能的话,他说不定会送个球球给你呢……

输入格式

输入有两行:

第一行一个正整数nn,表示小可可拥有的球球个数。
第二行有nn 个整数,第ii 个整数a[i]a[i]表示编号为ii 的球球的特点。

输出格式

输出一行,包括一个正整数,表示合法排列个数对109+710^9+7(即1000000007)取模的结果。

4
2 2 3 4
12

9
2 4 8 9 12 4 3 6 11
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%的数据满足:1n3001≤n≤3001a[i]1091≤a[i]≤10^9

本题共10 个测试点,编号为1~10,每个测试点额外保证如下:

测试点编号 n的范围 a[i]的范围
1~2 n10n≤10 a[i]109a[i]≤10^9
3~5 n300n≤300 1a[i]21≤a[i]≤2
6~8 - a[i]109a[i]≤10^9且都是质数
9~10 a[i]109a[i]≤10^9