#include <bits/stdc++.h>   #pragma GCC optimize( Ofast )   #pragma GCC optimize( inline )   using namespace std;   const int N = 405;   const int MOD = 1000000007;   int T, lim, n, k, l, p, cnt, id[N];   long long C[N][N], a[N], dp[N][N], fac[N] = {1};   vector<int> G[N];   bool Judge(long long x) {     long long k = sqrt(x);     return k * k == x;   }   void init() {     C[0][0] = 1LL;     for (int i = 1; i <= 350; i++) {       C[i][0] = C[i][i] = 1;       for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;       fac[i] = fac[i - 1] * i % MOD;     }     id[1] = cnt = 1, G[1].push_back(1);     for (int i = 2; i <= n; i++) {       bool flag = true;       for (int j = i - 1; j >= 1; j--)         if (Judge(a[j] * a[i])) {           G[id[j]].push_back(i);           id[i] = id[j];           flag = false;           break;         }       if (flag) {         id[i] = ++cnt;         G[cnt].push_back(i);       }     }   }   signed main() {     scanf( %d , &n);     for (int i = 1; i <= n; i++) scanf( %lld , a + i);     init();     dp[1][(int)G[1].size() - 1] = 1;     lim = (int)G[1].size();     for (int i = 2; i <= cnt; i++) {       int sz = G[i].size();       for (int k = 0; k < sz; k++)         for (int j = 0; j < lim; j++)           for (int p = 0; p <= min(j, k + 1); p++) {             dp[i][j + sz - k - 1 - p] += dp[i - 1][j] * C[sz - 1][k] % MOD *                                          C[j][p] % MOD *                                          C[lim + 1 - j][k + 1 - p] % MOD;             dp[i][j + sz - k - 1 - p] %= MOD;           }       lim += sz;     }     long long res = dp[cnt][0];     for (int i = 1; i <= cnt; i++) res = res * fac[(int)G[i].size()] % MOD;     printf( %lld n , res);     return 0;   }   