#include <bits/stdc++.h>
using namespace std;
const int maxn = 305, tt = 1e9 + 7;
int n, m, sum, a[maxn], g[maxn], s[maxn], fa[maxn];
long long ans, f[maxn][maxn], c[maxn][maxn], inv[maxn];
void make_c() {
  c[0][0] = 1ll;
  inv[0] = 1ll;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= i; j++)
      if (j == 0)
        c[i][j] = 1;
      else
        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % tt;
  for (int i = 1; i <= n; i++) fa[i] = i, inv[i] = 1ll * inv[i - 1] * i % tt;
}
int getfa(int x) {
  if (fa[x] != x) fa[x] = getfa(fa[x]);
  return fa[x];
}
void merge(int x, int y) {
  int fax = getfa(x), fay = getfa(y);
  if (fax != fay) fa[fax] = fay;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  make_c();
  for (int i = 1; i < n; i++)
    for (int j = i + 1; j <= n; j++) {
      long long sq = sqrt(1ll * a[i] * a[j]);
      if (sq * sq == 1ll * a[i] * a[j]) merge(i, j);
    }
  for (int i = 1; i <= n; i++) s[getfa(i)]++;
  for (int i = 1; i <= n; i++)
    if (s[i]) g[++m] = s[i];
  f[1][g[1] - 1] = 1ll;
  sum = g[1] - 1;
  for (int i = 2; i <= m; i++) {
    for (int j = 0; j <= sum; j++)
      for (int k = 0; k < g[i]; k++)
        for (int p = 0; p <= min(k + 1, j); p++)
          f[i][j - p + g[i] - k - 1] =
              (f[i][j - p + g[i] - k - 1] +
               f[i - 1][j] * c[g[i] - 1][k] % tt * c[j][p] % tt *
                   c[sum - j + 2][k + 1 - p] % tt) %
              tt;
    sum += g[i];
  }
  ans = f[m][0];
  for (int i = 1; i <= m; i++) ans = (ans * inv[g[i]]) % tt;
  printf("%lld\n", ans);
  return 0;
}
