#include <bits/stdc++.h>
const int MAXN = 330;
const int P = 1E9 + 7;
int d[MAXN], c[MAXN];
int fac[MAXN], ifac[MAXN];
int f[MAXN][MAXN];
int qpow(int n, int k) {
  int r = 1;
  while (k) {
    if (k & 1) r = 1ll * r * n % P;
    n = 1ll * n * n % P;
    k >>= 1;
  }
  return r;
}
inline int C(int n, int m) {
  if (m < 0 || m > n) return 0;
  return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;
}
int main() {
  int n, m = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    bool flag = 0;
    for (int j = 1; j <= m; j++) {
      int t = sqrt(1ll * d[j] * x);
      if (1ll * t * t == 1ll * d[j] * x) {
        c[j]++, flag = 1;
        break;
      }
    }
    if (!flag) d[++m] = x, c[m] = 1;
  }
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % P;
  ifac[n] = qpow(fac[n], P - 2);
  for (int i = n; i >= 1; i--) ifac[i - 1] = 1ll * ifac[i] * i % P;
  f[0][0] = 1;
  for (int i = 1, s = 0; i <= m; s += c[i++])
    for (int j = 0; j <= s; j++)
      for (int k = 1; k <= c[i]; k++)
        for (int l = 0; l <= j; l++)
          f[i][j + c[i] - k - l] =
              (f[i][j + c[i] - k - l] + 1ll * f[i - 1][j] * C(c[i] - 1, k - 1) %
                                            P * fac[c[i]] % P * C(j, l) % P *
                                            C(s - j + 1, k - l)) %
              P;
  printf("%d\n", f[m][0]);
  return 0;
}
