我们考虑当 $a_ia_j,a_ja_k$ 均为完全平方数的时候，$a_ia_ka_j^2$ 也一定是一个完全平方数，于是 $a_ia_k$ 也是完全平方数了。也就是说我们可以把所有数划分成很多类，每一类里面任意两个数乘起来都是完全平方，并且不同类的数乘起来一定不是完全平方。

如果把 “同一类” 这个问题看成 “同一种颜色”，现在问题就在于给定很多个数，每个数有自己的颜色，求排列数量满足不存在相邻的相同颜色的数。

这是个经典的容斥问题，可以考虑枚举不满足这个条件的相邻的数的数量。具体来说，我们分别处理一下每一种颜色。假设当前颜色的数个数为 $a_i$ ，把相邻的颜色相同的缩到一起，枚举一下缩到一起后的数的个数，容斥系数为 $(-1)^k$ 其中 $k$ 为缩到一起（也就是不满足条件）的个数，那么缩后形成的方案数量乘上容斥系数以及算上排列去重就是：

$$(-1)^{j} {a_i - 1 \choose j - 1} \frac 1 {(a_i-j)!}$$

现在问题就是我们要从每个颜色中选择一部分出来，把这个系数乘在一起，最后乘上 $k!$ ，就是缩成这么多个的总共的数量乘上容斥系数，加起来即可。

但是这样做了之后我们是将所有颜色视作相同的，但是在这个题还得给颜色分配标号，因此还得乘上所有颜色的阶乘的乘积。

这个东西可以通过分治 FFT / NTT 做到 $O(n\log n)$ ，但是既然出题人只给了 $n \le 300$ 就暴力 dp 就好了。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 316
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 1000000007
typedef long long ll;
int n;
int A[MAXN];

int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = 1ll * ret * x % P;
        x = 1ll * x * x % P , a >>= 1;
    }
    return ret;
}

bool chk( ll x ) {
    ll qwq = sqrt( x );
    return ( qwq * qwq == x );
}

int f[MAXN] , a[MAXN] , m;
int dp[MAXN][MAXN] , td[MAXN][MAXN] , J[MAXN] , iJ[MAXN];

int C( int a , int b ) {
    return a < b ? 0 : J[a] * 1ll * iJ[b] % P * iJ[a - b] % P;
}

void solve() {
    cin >> n;
    int flg;
    rep( i , 1 , n ) {
        scanf("%d",A + i);
        flg = 0;
        rep( j , 1 , i - 1 ) if( chk( 1ll * A[i] * A[j] ) ) {
            ++ a[f[j]] , flg = 1; break;
        }
        if( !flg ) f[i] = ++ m , a[m] = 1;
    }
    J[0] = iJ[0] = 1;
    rep( i , 1 , n ) J[i] = J[i - 1] * 1ll * i % P , iJ[i] = Pow( J[i] , P - 2 );
    int s = 0;
    dp[0][0] = 1;
    rep( i , 1 , m ) {
        rep( j , 0 , s ) {
            rep( t , 0 , a[i] - 1 ) {
                dp[i][j + a[i] - t] += 1ll * dp[i - 1][j] * ( ( t & 1 ) ? P - 1 : 1 ) % P * C( a[i] - 1 , t ) % P * iJ[a[i] - t] % P;
                dp[i][j + a[i] - t] %= P;
            }
        }
        s += a[i];
    }
    int res = 0;
    rep( i , 1 , n ) res = ( res + 1ll * J[i] * dp[m][i] % P ) % P;
    rep( i , 1 , m ) res = 1ll * res * J[a[i]] % P;
    cout << res << endl;
}

signed main() {
//    freopen("in1.in","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}