#include <bits/stdc++.h>
using namespace std;
const long long N = 309, mod = 1e9 + 7;
inline long long read() {
  register long long x = 0, f = 1;
  register char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + c - 48, c = getchar();
  }
  return x * f;
}
void pls(long long &x, long long y) {
  x += y;
  x = (x >= mod ? x - mod : x);
}
long long n, a[N], s[N];
namespace Solution_1 {
long long s[N], f[2][N][N];
void solve() {
  long long d = 0;
  for (register long long i = (1); i <= (n); i++) {
    if (a[i] == a[i - 1])
      s[i] = s[i - 1] + 1;
    else
      s[i] = 0;
  }
  f[0][0][0] = 1;
  for (register long long i = (1); i <= (n); i++) {
    if (a[i] != a[i - 1]) {
      for (register long long j = (0); j <= (i); j++)
        for (register long long k = (1); k <= (s[i - 1]); k++)
          pls(f[d ^ 1][j][0], f[d ^ 1][j][k]), f[d ^ 1][j][k] = 0;
    }
    for (register long long j = (0); j <= (i); j++) {
      long long upk = min(s[i], j);
      for (register long long k = (0); k <= (upk); k++) {
        if (j && k)
          pls(f[d][j][k], f[d ^ 1][j - 1][k - 1] * (2 * s[i] - k + 1) % mod);
        pls(f[d][j][k], f[d ^ 1][j][k] * (i - 2 * s[i] + 2 * k - j) % mod);
        pls(f[d][j][k], f[d ^ 1][j + 1][k] * (j - k + 1) % mod);
      }
    }
    memset(f[d ^ 1], 0, sizeof(f[d ^ 1]));
    if (i != n) d ^= 1;
  }
  printf("%lld\n", f[d][0][0]);
}
}  // namespace Solution_1
signed main() {
  n = read();
  for (register long long i = (1); i <= (n); i++) {
    a[i] = read();
    for (long long j = 2; j * j <= a[i]; j++)
      while (a[i] % (j * j) == 0) a[i] /= j * j;
  }
  sort(a + 1, a + n + 1);
  Solution_1::solve();
  return 0;
}
