#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char ch = getchar();
  int u = 0, f = 1;
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    u = (u << 1) + (u << 3) + ch - 48;
    ch = getchar();
  }
  return u * f;
}
int n;
const int mod = 1e9 + 7;
inline void add(int &x, int y) {
  x += y;
  x = (x >= mod ? x - mod : x);
}
inline void sub(int &x, int y) {
  x -= y;
  x = (x < 0 ? x + mod : x);
}
inline int pls(int x, int y) {
  x += y;
  return x >= mod ? x - mod : x;
}
inline int dec(int x, int y) {
  x -= y;
  return x < 0 ? x + mod : x;
}
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int fpw(int x, int y) {
  int r = 1;
  for (; y; y >>= 1, x = mul(x, x))
    if (y & 1) r = mul(r, x);
  return r;
}
const int maxn = 320;
int a[maxn];
int gp[maxn], tp, C[maxn][maxn], f[2][maxn], fac[maxn];
int main() {
  fac[0] = 1;
  for (int i = 1; i < maxn; ++i) fac[i] = mul(fac[i - 1], i);
  C[0][0] = 1;
  for (int i = 1; i < maxn; ++i) {
    for (int j = 1; j < i; ++j) C[i][j] = pls(C[i - 1][j - 1], C[i - 1][j]);
    C[i][0] = C[i][i] = 1;
  }
  n = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 1; i <= n; ++i)
    for (int j = 2; j * j <= a[i]; ++j)
      while (a[i] % (j * j) == 0) a[i] /= (j * j);
  sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; ++i)
    if (i == 1 || a[i] != a[i - 1])
      gp[++tp] = 1;
    else
      gp[tp]++;
  f[0][0] = 1;
  int sum = 0;
  int cur = 0;
  for (int i = 1; i <= tp; ++i) {
    cur ^= 1;
    for (int k = 0; k <= sum + 1; ++k) f[cur][k] = 0;
    for (int k = 1; k <= gp[i] && k <= sum + 1; ++k) {
      for (int j = 0; j <= sum; ++j) {
        for (int l = 0; l <= j && l <= k; ++l) {
          add(f[cur][j - l + gp[i] - k],
              mul(mul(mul(f[cur ^ 1][j], C[gp[i] - 1][k - 1]), C[j][l]),
                  C[sum + 1 - j][k - l]));
        }
      }
    }
    sum += gp[i];
  }
  int ans = f[cur][0];
  for (int i = 1; i <= tp; ++i) ans = mul(ans, fac[gp[i]]);
  printf("%d", ans);
  return 0;
}
