#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 550;
const long long mod = 1e9 + 7;
int n, a[maxn], sz;
long long dp[305][305], cnt[305], vis[305];
bool check(long long x) {
  long long l = 1, r = 1e9;
  while (l <= r) {
    long long mid = (l + r) / 2;
    if (mid * mid == x)
      return true;
    else if (mid * mid < x)
      l = mid + 1;
    else
      r = mid - 1;
  }
  return false;
}
inline long long quick_pow(long long x, int p) {
  long long res = 1;
  while (p) {
    if (p & 1) res = (res * x) % mod;
    x = (x * x) % mod, p >>= 1;
  }
  return res;
}
inline long long inv(long long a) {
  long long inv_a = quick_pow(a, mod - 2);
  return inv_a;
}
long long F[maxn], Finv[maxn];
void init() {
  F[0] = Finv[0] = 1ll;
  for (int i = 1; i <= maxn - 500; i++) {
    F[i] = F[i - 1] * 1ll * (long long)i % mod;
    Finv[i] = Finv[i - 1] * 1ll * inv(i) % mod;
  }
}
long long C(long long n, long long m) {
  if (m < 0 || m > n) return 0;
  return F[n] * 1ll * Finv[n - m] % mod * Finv[m] % mod;
}
int main() {
  cin >> n;
  init();
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    ++sz, cnt[sz] = 1, vis[i] = true;
    for (int j = 1; j <= n; j++) {
      if (vis[j]) continue;
      if (!check(1ll * a[i] * a[j])) continue;
      cnt[sz]++;
      vis[j] = true;
    }
  }
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  int m = 0;
  for (int i = 1; i <= sz; i++) {
    for (int j = 0; j <= m; j++) {
      for (int q = 1; q <= cnt[i]; q++) {
        for (int p = 0; p <= j; p++) {
          int k = j - p + cnt[i] - q;
          dp[i][k] += dp[i - 1][j] * C(cnt[i] - 1, q - 1) % mod * C(j, p) %
                      mod * C(m + 1 - j, q - p) % mod * F[cnt[i]] % mod;
          dp[i][k] %= mod;
        }
      }
    }
    m += cnt[i];
  }
  cout << dp[sz][0] << endl;
}
