#include <bits/stdc++.h>   using namespace std;   using ll = long long;   int const N = 200 * 1000 + 16;   int const M = 1000 * 1000 * 1000 + 7;   int n;   int a[320];   int f[616];   int ncr[616][616];   int dp[616][616];   struct dsu {     int fa[500];     dsu(int n) { iota(fa, fa + n + 10, 0); }     int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }     void unite(int x, int y) { fa[find(x)] = find(y); }   };   int main() {     cin.tie(0);     cin.sync_with_stdio(0);     cin >> n;     for (int i = 0; i < n; ++i) cin >> a[i];     dsu u(n);     for (int i = 0; i < n; ++i)       for (int j = i + 1; j < n; ++j) {         ll x = 1ll * a[i] * a[j];         ll s = sqrt(x) + 0.5;         if (s * s == x) u.unite(i, j);       }     memset(a, 0, sizeof a);     for (int i = 0; i < n; ++i) a[u.find(i)]++;     sort(a, a + n, greater<int>());     int m = find(a, a + n, 0) - a;     for (int i = 0; i < 616; ++i) ncr[i][0] = ncr[i][i] = 1;     for (int i = 1; i < 616; ++i)       for (int j = 1; j < i; ++j)         ncr[i][j] = (ncr[i - 1][j] + ncr[i - 1][j - 1]) % M;     f[0] = 1;     for (int i = 1; i < 616; ++i) f[i] = 1ll * i * f[i - 1] % M;     dp[0][a[0] - 1] = 1;     int k = a[0];     for (int i = 1; i < m; ++i) {       int len = a[i];       for (int p = 0; p < k; ++p) {         int x = dp[i - 1][p];         if (not x) continue;         for (int g = 1; g <= len; ++g) {           for (int u = min({len, p, g}); u >= 0; --u) {             ll y = 1ll * ncr[k - p + 1][g - u] * ncr[p][u] % M;             y *= ncr[len - 1][g - 1];             y %= M;             dp[i][p - u + len - g] += x * y % M;             dp[i][p - u + len - g] %= M;           }         }       }       k += len;     }     int ans = dp[m - 1][0];     for (int i = 0; i < m; ++i) ans = 1ll * ans * f[a[i]] % M;     cout << ans;   }   