#include <bits/stdc++.h>
namespace IO {
char buf[1000000], *p1, *p2;
inline char getc() {
  if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
  return p1 == p2 ? EOF : *(p1++);
}
template <typename tp>
inline void r(tp &n) {
  n = 0;
  char c = getc();
  while (!isdigit(c)) c = getc();
  while (isdigit(c)) n = n * 10 + c - 48, c = getc();
}
template <typename tp, typename... Args>
inline void r(tp &n, Args &...args) {
  r(n);
  r(args...);
}
template <typename tp>
inline void write(tp n) {
  if (n / 10) write(n / 10);
  putchar(n % 10 + 48);
}
template <typename tp>
inline void w(tp n, char c = '\n') {
  write(n);
  putchar(c);
}
};  // namespace IO
using namespace IO;
const int N = 3e2 + 5, M = 1e5, mod = 1e9 + 7;
using namespace std;
int n, num, tot;
int a[N], c[N], o[M], h[N], f[N], fac[N], inv[N], invf[N], g[N][N];
long long p[M];
void Prework(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!o[i]) p[++num] = i;
    for (int j = 1; j <= num and p[j] * i <= n; ++j) {
      o[p[j] * i] = 1;
      if (i % p[j] == 0) break;
    }
  }
  for (int i = 1; i <= num; ++i) p[i] = p[i] * p[i];
}
int binom(int n, int m) {
  if (n < 0 or m < 0 or n - m < 0) return 0;
  return 1ll * fac[n] * invf[m] % mod * invf[n - m] % mod;
}
int main() {
  Prework(1e5);
  r(n);
  fac[0] = fac[1] = inv[0] = inv[1] = invf[0] = invf[1] = 1;
  for (int i = 2; i <= n; ++i)
    fac[i] = 1ll * i * fac[i - 1] % mod,
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod,
    invf[i] = 1ll * invf[i - 1] * inv[i] % mod;
  for (int i = 1; i <= n; ++i) {
    r(a[i]);
    for (int j = 1; p[j] <= a[i]; ++j)
      while (a[i] % p[j] == 0) a[i] /= p[j];
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i)
    if (a[i] != a[i - 1])
      c[++tot] = 1;
    else
      ++c[tot];
  for (int i = 1; i <= tot; ++i)
    for (int j = 1; j <= c[i]; ++j)
      g[i][c[i] - j] =
          1ll * binom(c[i] - 1, j - 1) * fac[c[i]] % mod * invf[j] % mod;
  int len = 1;
  f[0] = 1;
  for (int i = 1; i <= tot; ++i) {
    memset(h, 0, sizeof h);
    for (int k = 0; k < len; ++k)
      for (int j = 0; j < c[i]; ++j)
        (h[k + j] += 1ll * f[k] * g[i][j] % mod) %= mod;
    len += c[i] - 1;
    for (int k = 0; k < len; ++k) f[k] = h[k];
  }
  int ans = 0;
  for (int i = 0; i < len; ++i)
    if (i & 1)
      ans = (ans + mod - 1ll * f[i] * fac[n - i] % mod) % mod;
    else
      ans = (ans + 1ll * f[i] * fac[n - i] % mod) % mod;
  w(ans);
  return 0;
}
