#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 1e9 + 7;
const long long maxn = 300 + 7;
const double eps = 0.00000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline T powMM(T a, T b) {
  T ret = 1;
  for (; b; b >>= 1ll, a = a * a % M)
    if (b & 1) ret = 1ll * ret * a % M;
  return ret;
}
map<int, int> MP;
int a[maxn];
long long dp[maxn][maxn];
long long fac[maxn], inv[maxn];
inline long long C(int n, int m) {
  if (n < m) return 0;
  return fac[n] * inv[m] % M * inv[n - m] % M;
}
int tot;
int n, m;
int i, j, s, d;
int main() {
  fac[0] = 1;
  for (i = 1; i <= 300; i++) fac[i] = fac[i - 1] * i % M;
  inv[0] = inv[1] = 1;
  for (i = 2; i <= 300; i++) inv[i] = (M - M / i) * inv[M % i] % M;
  for (i = 1; i <= 300; i++) inv[i] = inv[i] * inv[i - 1] % M;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    int val;
    scanf("%d", &val);
    for (j = 2; j * j <= val; j++)
      while (val % (j * j) == 0) val /= j * j;
    MP[val]++;
  }
  for (auto now : MP) a[m++] = now.second;
  dp[0][0] = 1;
  for (i = 0; i < m; i++) {
    for (j = 0; j <= tot; j++)
      if (dp[i][j]) {
        for (s = 1; s <= a[i]; s++) {
          for (d = 0; d <= min(j, s); d++) {
            dp[i + 1][j - d + a[i] - s] =
                (dp[i + 1][j - d + a[i] - s] +
                 dp[i][j] * fac[a[i]] % M * C(a[i] - 1, s - 1) % M * C(j, d) %
                     M * C(tot + 1 - j, s - d) % M) %
                M;
          }
        }
      }
    tot += a[i];
  }
  printf("%I64d\n", dp[m][0]);
}
