#include <bits/stdc++.h>
using namespace std;
const int N = 305;
const int mod = 1e9 + 7;
int a[N], n;
template <typename T>
inline void red(T &x) {
  x = 0;
  bool fg = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') fg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (T)(ch ^ 48), ch = getchar();
  if (fg) x = -x;
}
bool issqrt(long long x) {
  long long t = sqrt(x);
  return t * t == x;
}
int id[N], tot, cnt[N];
long long f[N][N], inv[N * 3] = {1, 1}, fac[N * 3] = {1, 1},
                           invfac[N * 3] = {1, 1};
long long C(int n, int m) {
  if (m == -1) return 1;
  return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
void add(long long &x, long long y) {
  y %= mod;
  x += y;
  x %= mod;
}
int main() {
  red(n);
  for (int i = 1; i <= n; i++) red(a[i]);
  for (int i = 1; i <= n; i++)
    if (!id[i]) {
      id[i] = ++tot;
      cnt[tot] = 1;
      for (int j = i + 1; j <= n; j++)
        if (!id[j]) {
          if (issqrt(1ll * a[i] * a[j])) id[j] = tot, cnt[tot]++;
        }
    }
  for (int i = 2; i <= n * 3; i++)
    fac[i] = (fac[i - 1] * i) % mod,
    inv[i] = (mod - mod / i) * inv[mod % i] % mod,
    invfac[i] = invfac[i - 1] * inv[i] % mod;
  f[1][cnt[1] - 1] = fac[cnt[1]];
  int size = 0;
  for (int i = 1; i < tot; i++) {
    size += cnt[i];
    for (int j = 0; j <= size; j++) {
      if (f[i][j] == 0) continue;
      for (int D = 0; D <= min(j, cnt[i + 1]); D++) {
        for (int E = 0; E <= (size + 1 - j) && (D + E) <= cnt[i + 1]; E++) {
          if (D + E == 0) continue;
          add(f[i + 1][j + cnt[i + 1] - 2 * D - E],
              f[i][j] * fac[cnt[i + 1]] % mod * C(j, D) % mod *
                  C(size + 1 - j, E) % mod * C(cnt[i + 1] - 1, D + E - 1) %
                  mod);
        }
      }
    }
  }
  printf("%lld\n", f[tot][0]);
}
