#include <bits/stdc++.h>
using namespace std;
const int N = 300 + 5;
const long long P = 1e9 + 7;
inline long long Pow(long long a, long long anum) {
  long long ret = 1ll;
  while (anum) {
    if (anum & 1) ret = ret * a % P;
    a = a * a % P;
    anum >>= 1ll;
  }
  return ret;
}
map<int, int> ms;
int n, gn, a[N], gr[N];
long long fac[N], rfac[N];
inline void Init() {
  int now, ed;
  fac[0] = 1ll;
  for (int i = (1); i <= (int)(n); ++i) {
    now = a[i];
    ed = sqrt(now);
    for (int j = (2); j <= (int)(ed); ++j) {
      if (1ll * j * j > a[i]) break;
      while (!(now % (j * j))) now /= j * j;
    }
    if (!ms.count(now)) ms[now] = ++gn;
    ++gr[ms[now]];
    fac[i] = fac[i - 1] * i % P;
  }
  rfac[n] = Pow(fac[n], P - 2);
  for (int i = (n - 1); i >= (int)(0); --i) rfac[i] = rfac[i + 1] * (i + 1) % P;
}
long long f[N][N];
long long C(int x, int y) {
  if (y > x) return 0;
  return fac[x] * rfac[y] % P * rfac[x - y] % P;
}
int main() {
  scanf("%d", &n);
  for (int i = (1); i <= (int)(n); ++i) scanf("%d", &a[i]);
  Init();
  f[0][0] = 1ll;
  int mg, nj, tot = 1;
  for (int i = (0); i <= (int)(gn - 1); ++i) {
    tot += gr[i];
    mg = gr[i + 1];
    for (int j = (0); j <= (int)(n); ++j)
      if (f[i][j]) {
        for (int k = (1); k <= (int)(min(mg, tot)); ++k)
          for (int l = (0); l <= (int)(min(j, k)); ++l) {
            nj = j - l + (mg - k);
            f[i + 1][nj] += f[i][j] * fac[mg] % P * C(j, l) % P *
                            C(tot - j, k - l) % P * C(mg - 1, k - 1) % P;
            f[i + 1][nj] %= P;
          }
      }
  }
  printf("%I64d\n", f[gn][0]);
  return 0;
}
