#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;
}
