#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct buf {
  char B[23000005], *s;
  buf() : s(B) { fread(B, 1, 23000000, stdin); }
  operator int() {
    int x = 0;
    while (*s < '0' || *s > '9') s++;
    while (*s >= '0' && *s <= '9') x = x * 10 + *s++ - 48;
    return x;
  }
} it;
int b[512];
int a[512];
int C[350][350];
int fac[350];
int dp[350][350];
map<int, int> dat;
int getint() {
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  int x = 0;
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x;
}
int main() {
  int n;
  n = it;
  dat.clear();
  for (int i = (1); i <= (n); i++) {
    a[i] = it;
    for (int j = 2; j <= a[i] / j; j++) {
      while (a[i] % (j * j) == 0) {
        a[i] /= (j * j);
      }
    }
    dat[a[i]]++;
  }
  fac[0] = 1;
  for (int i = (1); i <= (n); i++) fac[i] = (1LL * fac[i - 1] * i) % mod;
  int m = 0;
  for (auto iter : dat) {
    m++;
    b[m] = iter.second;
  }
  C[0][0] = 1;
  for (int i = (1); i <= (300); i++) {
    C[i][0] = 1;
    for (int j = (1); j <= (i); j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  }
  dp[1][b[1] - 1] = 1;
  int s = 0;
  int ans = 1;
  for (int i = (1); i <= (m); i++) {
    s += b[i];
    for (int j = (0); j <= (n - 1); j++)
      if (dp[i][j]) {
        for (int ii = (1); ii <= (b[i + 1]); ii++) {
          for (int jj = (0); jj <= (min(j, ii)); jj++) {
            dp[i + 1][j - jj + b[i + 1] - ii] +=
                1LL * dp[i][j] % mod * C[b[i + 1] - 1][ii - 1] % mod *
                C[j][jj] % mod * C[s + 1 - j][ii - jj] % mod;
            dp[i + 1][j - jj + b[i + 1] - ii] %= mod;
          }
        }
      }
    ans = (1LL * ans * fac[b[i]]) % mod;
  }
  ans = (1LL * ans * dp[m][0]) % mod;
  printf("%d\n", ans);
  return 0;
}
