#include <bits/stdc++.h>
template <class _Tp = int>
inline _Tp read() {
  _Tp w = 0;
  bool f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) w = (w << 3) + (w << 1) + (ch ^ 48), ch = getchar();
  return f ? -w : w;
}
const int mod = 1e9 + 7, kMaxN = 3e2 + 5;
int n;
long long a[kMaxN], f[2][kMaxN][kMaxN];
long long Get(long long a) {
  for (int i = 2; i * i <= a; i++)
    while (a % (i * i) == 0) a /= i * i;
  return a;
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = Get(read());
  a[0] = -1;
  std::sort(a + 1, a + n + 1);
  f[1][0][0] = 1;
  int x = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] ^ a[i - 1])
      for (int k = 1; k <= x; k++)
        for (int j = 0; j <= i; j++)
          f[(i & 1) ^ 1][j][0] =
              (f[(i & 1) ^ 1][j][0] + f[(i & 1) ^ 1][j][k]) % mod,
                      f[(i & 1) ^ 1][j][k] = 0;
    x = (a[i] ^ a[i - 1]) ? 0 : x + 1;
    for (int j = 0; j <= i; j++) {
      int upper = std::min(x, j);
      for (int k = 0; k <= upper; k++) {
        f[(i & 1)][j][k] =
            (f[(i & 1)][j][k] + f[(i & 1) ^ 1][j + 1][k] * (j - k + 1)) % mod;
        f[(i & 1)][j][k] = (f[(i & 1)][j][k] +
                            f[(i & 1) ^ 1][j][k] * (i - j - 2 * x + 2 * k)) %
                           mod;
        if (!k || !j) continue;
        f[(i & 1)][j][k] = (f[(i & 1)][j][k] +
                            f[(i & 1) ^ 1][j - 1][k - 1] * (2 * x - k + 1)) %
                           mod;
      }
    }
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= n; k++) f[(i & 1) ^ 1][j][k] = 0;
  }
  printf("%lld\n", f[n & 1][0][0]);
}
