#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long a[305];
int prt[305], num[305] = {0}, ha[305] = {0};
long long f[305][605] = {0};
long long c[305][305], jc[305];
int n;
bool pd(int i, int j) {
  long long ha = sqrt(a[i] * a[j]);
  if (ha * ha == a[i] * a[j]) return true;
  return false;
}
int getfa(int x) {
  if (x == prt[x]) return x;
  return prt[x] = getfa(prt[x]);
}
void init() {
  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;
  }
  jc[0] = 1;
  for (int i = 1; i <= 300; i++) jc[i] = jc[i - 1] * i % mod;
}
void solve() {
  int i, j, k, h;
  int sum = num[1];
  f[1][num[1] - 1] = 1;
  for (i = 2; i <= num[0]; i++) {
    for (j = 0; j <= sum - 1; j++)
      for (k = 1; k <= num[i]; k++)
        for (h = 0; h <= j && h <= k; h++) {
          f[i][j - h + num[i] - k] += f[i - 1][j] * c[j][h] % mod *
                                      c[num[i] - 1][k - 1] % mod *
                                      c[sum + 1 - j][k - h] % mod;
          f[i][j - h + num[i] - k] %= mod;
        }
    sum += num[i];
  }
  long long ans = f[num[0]][0];
  for (int i = 1; i <= num[0]; i++) ans = ans * jc[num[i]] % mod;
  printf("%lld\n", ans);
}
int main() {
  init();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  for (int i = 1; i <= n; i++) prt[i] = i;
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      if (pd(i, j)) {
        int f1, f2;
        f1 = getfa(i);
        f2 = getfa(j);
        if (f1 != f2) prt[f1] = f2;
      }
  for (int i = 1; i <= n; i++) prt[i] = getfa(i);
  for (int i = 1; i <= n; i++) {
    if (ha[prt[i]] == 0) {
      num[0]++;
      ha[prt[i]] = num[0];
      num[num[0]]++;
    } else
      num[ha[prt[i]]]++;
  }
  solve();
  return 0;
}
