#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  return f ? -x : x;
}
void write(long long x) {
  if (x < 0) x = -x, putchar('-');
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
const long long mod = 1e9 + 7;
long long f[310][310], c[310][310], n, a[310], fac[310], mark[310], b[310], m;
long long sqr(long long x) { return x * x; }
void add(long long &a, long long b) { a = (a + b) % mod; }
int main() {
  n = read();
  for (long long i = 1; i <= 300; ++i) {
    c[i][0] = c[i][i] = 1;
    for (long long j = 1; j <= i - 1; ++j)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
  }
  c[0][0] = fac[0] = 1;
  for (long long i = 1; i <= 300; ++i) fac[i] = fac[i - 1] * i % mod;
  for (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))) a[i] /= j * j;
  }
  for (long long i = 1; i <= n; ++i)
    if (!mark[i]) {
      b[++m] = 1;
      for (long long j = i + 1; j <= n; ++j)
        if (!mark[j] && (a[i] == a[j])) b[m]++, mark[j] = 1;
    }
  f[1][b[1] - 1] = 1;
  long long sum = b[1];
  for (long long i = 2; i <= m; ++i) {
    for (long long j = 0; j <= sum - 1; ++j)
      for (long long k = 0; k <= b[i] - 1; ++k)
        for (long long l = 0; l <= min(j, k + 1); ++l)
          add(f[i][j + b[i] - 1 - k - l], f[i - 1][j] * c[b[i] - 1][k] % mod *
                                              c[j][l] % mod *
                                              c[sum - 1 - j + 2][k + 1 - l]);
    sum += b[i];
  }
  for (long long i = 1; i <= m; ++i) f[m][0] = (f[m][0] * fac[b[i]]) % mod;
  writeln(f[m][0]);
}
