<h2>题目大意</h2>

给你一个长度为 $n$ 的序列，问你有多少种置换，使得置换后的序列相邻两项的乘积都不是平方数。

<h2>题解</h2>

这个题目好像比较厉害的样子。。首先把这些数按照是否能组成平方数分组，同一组里都是两两相乘能凑成平方数的，可以证明存在这样的分配方案。
然后我们可以设 $f_{i,j}$ 表示插入了前 $i$ 个组，有 $j$ 个不满足的相邻关系的方案数。
我们令 $tot$ 表示已经填完的个数，$sz$表示这一组的大小，$d$ 表示该次插入隔开了原来多少个组，$k$ 表示将这些数分成了多少组。我们不考虑顺序，能得到转移：
$$f_{i-1,j}* T \to f_{i,j-d+sz-k}$$
其中
$$T = \binom {sz-1} {k-1} \binom j d \binom {tot-j+1} {k-d}$$
然后最后答案乘上每组的阶乘，就好了。

/*
 * Author: RainAir
 * Time: 2019-08-28 08:59:34
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 300+5;
const int ha = 1e9 + 7;
int fac[MAXN],inv[MAXN];

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1llresa%ha;
        a = 1llaa%ha;
        n >>= 1;
    }
    return res;
}

inline void prepare(){
    fac[0] = 1;
    FOR(i,1,MAXN-1) fac[i] = 1llfac[i-1]i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);
    ROF(i,MAXN-2,0) inv[i] = 1llinv[i+1](i+1)%ha;
}

inline int C(int n,int m){
    if(n < m) return 0;
    if(!m) return 1;
    return 1llfac[n]inv[m]%ha*inv[n-m]%ha;
}


int n,a[MAXN];
bool vis[MAXN];int sz[MAXN],cnt;
int fMAXN;

inline int pd(int x){
    int q = std::sqrt(1.0*x);
    return q*q == x;
}

signed main(){
    scanf("%lld",&n);prepare();
    FOR(i,1,n) scanf("%lld",a+i);
    FOR(i,1,n){
        if(vis[i]) continue;
        sz[++cnt] = 1;vis[i] = true;
        FOR(j,1,n){
            if(vis[j]) continue;
            if(pd(a[i]*a[j])){
                vis[j] = true;sz[cnt]++;
            }
        }
    }
    f0 = 1;int tot = 0;
    FOR(i,1,cnt){
        FOR(j,0,tot){
            FOR(k,1,std::min(sz[i],tot+1)){
                FOR(d,0,std::min(j,k)){
                    int T = C(j,d)C(sz[i]-1,k-1)%haC(tot-j+1,k-d)%ha;
                    (fi-k] += fi-1*T%ha)%=ha;
                }
            }
        }
        tot += sz[i];
    }
    int ans = fcnt;
    FOR(i,1,cnt) ans = 1llansfac[sz[i]]%ha;
    printf("%lldn",ans);
    return 0;
}