#include <bits/stdc++.h>
using namespace std;
const long long inf = 1LL << 61;
const long long mod = 1000000007;
const int maxn = 310;
long long f[maxn], invf[maxn], dp[maxn][maxn], a[maxn];
int vis[maxn], cnt[maxn];
long long extgcd(long long a, long long b, long long &x, long long &y);
long long inv(long long a, long long n);
void init();
bool check(long long x);
long long C(int n, int m);
int main() {
  std::ios::sync_with_stdio(false);
  int i = 0, j = 0, k = 0;
  int n, sz = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  memset(vis, 0, sizeof(vis)), memset(cnt, 0, sizeof(cnt));
  init();
  for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    vis[i] = true;
    sz++;
    cnt[sz] = 1;
    for (int j = i + 1; j <= n; j++) {
      if (vis[j]) continue;
      if (check(a[i] * a[j])) {
        vis[j] = true;
        cnt[sz]++;
      }
    }
  }
  memset(dp, 0, sizeof(dp));
  int m = cnt[1] - 1;
  dp[1][m] = 1;
  for (int i = 2; i <= sz; i++) {
    for (int j = 0; j < maxn; j++) {
      if (dp[i - 1][j] == 0) continue;
      for (int k = 0; k < cnt[i]; k++) {
        for (int p = 0; p <= min(k + 1, j); p++) {
          long long tmp = dp[i - 1][j] * C(cnt[i] - 1, k) % mod * C(j, p) %
                          mod * C(m + 2 - j, k + 1 - p) % mod;
          dp[i][j + cnt[i] - 1 - k - p] =
              (dp[i][j + cnt[i] - 1 - k - p] + tmp) % mod;
        }
      }
    }
    m += cnt[i];
  }
  long long ans = dp[sz][0];
  for (int i = 1; i <= sz; i++) ans = ans * f[cnt[i]] % mod;
  printf("%lld\n", ans);
  return 0;
}
long long C(int n, int m) {
  long long ans = 1;
  ans = f[n];
  ans = ans * invf[m] % mod * invf[n - m] % mod;
  return ans;
}
void init() {
  f[0] = 1;
  invf[0] = inv(1, mod);
  for (int i = 1; i < maxn; i++) {
    f[i] = f[i - 1] * i % mod;
    invf[i] = inv(f[i], mod);
  }
}
bool check(long long x) {
  long long m = sqrt(x);
  for (long long i = max(m - 5, 1LL); i < m + 5; i++) {
    if (i * i == x) return true;
  }
  return false;
}
long long extgcd(long long a, long long b, long long &x, long long &y) {
  long long d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1, y = 0;
  }
  return d;
}
long long inv(long long a, long long n) {
  long long d, x, y;
  d = extgcd(a, n, x, y);
  return d == 1 ? (x + n) % n : -1;
}
