#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const long long mod = 1e9 + 7;
int n, c[505], d[505][505], fa[505], a[505];
long long dp[505][505], comb[505][505];
int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
void Union(int u, int v) {
  int x = Find(u);
  int y = Find(v);
  if (x != y) fa[x] = y;
}
int is(int i, int j) {
  long long x = 1LL * a[i] * a[j];
  long long y = sqrt(1.0 * x);
  if (y * y == x) return 1;
  return 0;
}
int main() {
  for (int j = 0; j < 505; j++) comb[0][j] = 0;
  for (int i = 0; i < 505; i++) comb[i][0] = 1;
  for (int i = 1; i < 505; i++)
    for (int j = 1; j < 505; j++)
      comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % mod;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  memset(d, 0, sizeof(d));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == j) continue;
      if (is(i, j)) d[i][j] = 1;
    }
  }
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      if (d[i][k])
        for (int j = 1; j <= n; j++) d[i][j] = d[i][j] || d[k][j];
  for (int i = 1; i <= n; i++) fa[i] = i;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == j) continue;
      if (d[i][j]) Union(i, j);
    }
  }
  vector<int> g[505];
  for (int i = 1; i <= n; i++) g[Find(i)].push_back(i);
  int cnt = 0;
  for (int i = 1; i <= n; i++)
    if (g[i].size() != 0) c[++cnt] = g[i].size();
  int N = cnt;
  dp[0][0] = 1;
  int all = 1;
  for (int x = 1; x <= N; x++) {
    for (int ij = 1; ij <= c[x]; ij++) {
      for (int y = 0; y <= all; y++) {
        if (dp[x - 1][y] > 0) {
          for (int j = 0; j <= min(ij, y); j++) {
            int i = ij - j;
            int z = all - y;
            long long add = dp[x - 1][y] * comb[y][j] % mod;
            add = add * comb[z][i] % mod;
            add = add * comb[c[x] - 1][ij - 1] % mod;
            dp[x][(y - j) + (c[x] - ij)] =
                (dp[x][(y - j) + (c[x] - ij)] + add) % mod;
          }
        }
      }
    }
    all += c[x];
  }
  long long ans = dp[N][0];
  for (int i = 1; i <= N; i++) {
    long long tmp = 1LL;
    for (int j = 1; j <= c[i]; j++) tmp = tmp * j % mod;
    ans = ans * tmp % mod;
  }
  printf("%I64d\n", ans);
  return 0;
}
