如果这不是一道原题，这道题出的还不错，是个比较毒瘤的数数。由于我太菜了反正我自己没有做出来后面的 dp，zyf 巨佬教的。
不过听说合肥六中某巨佬当年也没做出来，平衡了雾
但问题是这道题是原题，我安徽人什么时候可以真正站起来（恼
首先我们会发现这道题很不好入手，所以我们考虑部分分，很容易发现 6-8 测试点 \(a_i\) 全是质数。在这些测试点里面，我们只需要相邻两个球颜色不同即可。
我的数学老师说过，没有无缘无故的爱与恨，也没有无缘无故的部分分。所以我们考虑把 \(a_i\) 为合数的情况转化成 \(a_i\) 的情况。
这个时候就容易想到这个：如果 \(xy\) 为完全平方数，\(yz\) 为完全平方数，那么 \(xz\) 也是完全平方数。证明显而易见。这个引理告诉我们，如果 \(a_i\times a_j\) 为完全平方数，\(a_j \times a_k\) 为完全平方数，\(a_i \times a_k\) 也是完全平方数。也就是说这种数字不能放在一起。如果是更多个数字也是同理。
也就是说我们可以用暴力预处理出来哪些数不能放在一起，放在一个集合里，每个集合里的数有专属的颜色，那么我们的问题就是和 \(a_i\) 是质数的部分分的问题等价了：我们有 \(n\) 个球球 \(k\) 种颜色，第 \(i\) 个颜色有 \(s_i\) 个球，相同颜色的球不能放在一起，求方案数。
然后就是我没做出来的 dp（(*/ω＼*)），说实话也不难
我们容易想到这样一个 dp，\(f_i\) 为前 \(i\) 种颜色的合法方案数。把从 \(i - 1\) 转移到 \(i\) 就是把 \(s_i\) 个球球插入到缝隙里面。
但是这样不能转移，炒个例子，\(i\) 从 \(3\) 转移到 \(4\)，\(i = 3\) 可能是 1 1 2 3，\(i = 4\) 就是在里面添加一个 4 在前两个 1 里面，变成 1 4 1 2 3，这是合法的。
这也给我们启发，当我们添加球的时候，可能会抵消掉前面一些不合法的空隙（不合法的空隙就是两边颜色相同的空隙）。
因此我们可以也把不合法的空隙也加入状态中，\(f_{i, j}\) 为前 \(i\) 种颜色有 \(j\) 个不合法空隙。
然后我们就可以考虑转移了。
受到上面的启发，我们会发现加入球球的时候我们会新增一些非法空隙，也会抵消原来的一些非法空隙。
因此我们设新增了 \(new\) 个非法空隙，抵消了 \(del\) 个非法空隙。我们的转移就是从 \(f_{i - 1,j}\) 到 \(f_{i, j - del+new}\)。
容易发现“新增”和“抵消”是两个基本独立的问题，因此我们考虑对着两个问题分别计数，然后乘起来。
先考虑在 \(s_i\) 个球球里新增了 \(new\) 个非法空隙。炒个例子，\(i = 7, s_i = 7, new = 3\)，则一种方案是 7|7|7 7|7 7 7，| 代表非法空隙。我们不难发现这个就是把 \(s_i\) 个球球划分成 \((s_i - new)\) 个块，插班可得方案数为 \(C_{s_i - 1}^{s_i - new - 1}\)。
再考虑抵消 \(del\) 个，我们令 \(s_i\) 的前缀和数组为 \(tot_i\)，即前 \(i\) 种颜色一共有多少个。首先我们要找 \(del\) 个原来就有的非法空隙占掉，方案数 \(C_{j}^{del}\)。然后还有 \((new - del)\) 个，能够插在合法的 \(tot_{i - 1} - j + 1\) 个空中（因为这里的空是开头的前面和最后的后面都能插入，所以是 \(tot_{i - 1} - j + 1\) 个空位），所以是 \(C_{new - del}^{tot_{i - 1} - j + 1}\)。
因此就有这样的转移 \(f_{i, j + new - del} += f_{i - 1, j}\times C_{s_i - 1}^{s_i - new - 1} \times C_{j}^{del}\times C_{new - del}^{tot_{i - 1} - j + 1}\)
细节略多，然后我自个打的时候反复身败名裂，感谢 zyf 巨佬的调代码的帮助 qwq
//SIXIANG
#include <iostream>
#include <cmath>
#define MAXN 300
#define LL long long
#define QWQ cout << "QWQ" << endl;
using namespace std;
const LL Mod = 1e9 + 7;
LL c[310][310], f[310][310], frac[310];
bool judge(LL x) {
LL l = 1, r = x, mid;
while(l <= r) {
mid = (l + r) >> 1;
LL sqr = mid * mid;
if(sqr == x) return 1;
if(sqr > x) r = mid - 1;
else l = mid + 1;
}
return 0;
}
int a[MAXN + 10], cl[MAXN + 10], cnt = 0;
LL s[MAXN + 10], tot[MAXN + 10];
LL C(int n, int m) {
if(n < m) return 0;
else return c[n][m];
}
int main() {
c[0][0] = 1, c[1][0] = c[1][1] = 1;
frac[0] = 1;
for(int p = 2; p <= 300; p++) {
c[p][0] = 1;
for(int i = 1; i <= p; i++)
c[p][i] = (c[p - 1][i - 1] + c[p - 1][i]) % Mod;
}
for(int p = 1; p <= 300; p++)
frac[p] = frac[p - 1] * p % Mod;
int n; cin >> n;
for(int p = 1; p <= n; p++)
cin >> a[p];
for(int p = 1; p <= n; p++) {
for(int i = 1; i < p; i++) {
if(judge(1ll * a[p] * a[i])) {
if(cl[i]) cl[p] = cl[i];
else cl[p] = cl[i] = ++cnt;
}
}
if(!cl[p]) cl[p] = ++cnt;
}
for(int p = 1; p <= n; p++)
s[cl[p]]++;
for(int p = 1; p <= cnt; p++)
tot[p] = tot[p - 1] + s[p];
f[1][tot[1] - 1] = 1;
for(int i = 2; i <= cnt; i++)
for(int j = 0; j < tot[i - 1]; j++)
for(int ne = 0; ne < s[i]; ne++)
for(int de = 0; de + ne <= s[i]; de++) {
if(j + ne - de < 0) continue;
f[i][j + ne - de] += f[i - 1][j] * C(s[i] - 1, s[i] - ne - 1) % Mod
* C(j, de) % Mod * C(tot[i - 1] - j + 1, s[i] - ne - de) % Mod;
f[i][j + ne - de] %= Mod;
}
for(int p = 1; p <= cnt; p++)
f[cnt][0] = f[cnt][0] * 1ll * frac[s[p]] % Mod;
cout << f[cnt][0] << endl;
}