#include <bits/stdc++.h>
using namespace std;
const int N = 305;
const int mod = 1e9 + 7;
int a[N], dp[N][N], C[N][N], belong[N], cnt[N], sum[N], fac[N];
bool f(long long x) {
  long long l = 1, r = 1e9 + 5;
  while (l < r) {
    long long mid = (l + r) / 2;
    if (mid * mid < x)
      l = mid + 1;
    else
      r = mid;
  }
  return l * l == x;
}
void init() {
  C[0][0] = 1;
  for (int i = 1; i < N; i++) {
    C[i][0] = 1;
    for (int j = 1; j < N; j++) {
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
  }
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
}
int main() {
  int n;
  init();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  int tot = 0;
  for (int i = 1; i <= n; i++) {
    if (!belong[i]) {
      belong[i] = ++tot;
      for (int j = i + 1; j <= n; j++) {
        if (f(1ll * a[i] * a[j]) && !belong[j]) {
          belong[j] = tot;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    cnt[belong[i]]++;
  }
  for (int i = 1; i <= tot; i++) sum[i] = sum[i - 1] + cnt[i];
  dp[0][0] = 1;
  for (int i = 0; i < tot; i++) {
    int s = sum[i] + 1;
    for (int j = 0; j <= s; j++) {
      if (!dp[i][j]) continue;
      for (int k = 1; k <= cnt[i + 1]; k++) {
        for (int l = 0; l <= min(j, k); l++) {
          (dp[i + 1][j - l + cnt[i + 1] - k] +=
           1ll * fac[cnt[i + 1]] * dp[i][j] % mod * C[j][l] % mod *
           C[s - j][k - l] % mod * C[cnt[i + 1] - 1][k - 1] % mod) %= mod;
        }
      }
    }
  }
  printf("%d\n", dp[tot][0]);
  return 0;
}
